递归+最短路径 | HJ43 迷宫问题

import copy
def func(migong, i, j, path):
    if (i, j) == (n-1, m-1):
        res.append(copy.deepcopy(path))
        return
    if j+1 < m and migong[i][j+1] != '1' and (i,j+1)not in path:
        path.append((i, j+1))
        func(migong, i, j+1, path)
        path.pop()
    if i+1 < n and migong[i+1][j] != '1' and (i+1,j)not in path:
        path.append((i+1, j))
        func(migong, i+1, j, path)
        path.pop()
    if j-1 >= 0 and migong[i][j-1] != '1' and (i,j-1)not in path:
        path.append((i, j-1))
        func(migong, i, j-1, path)
        path.pop()
    if i-1 >= 0 and migong[i-1][j] != '1' and (i-1,j)not in path:
        path.append((i-1, j))
        func(migong, i-1, j, path)
        path.pop()

while True:
    try:
        n, m = list(map(int, input().split(' ')))
        migong = []
        res = []
        for _ in range(n):
            migong.append(input().split(' '))
        func(migong, 0, 0, [(0,0)])
        min_length, min_path = n*m, None
        for path in res:
            if len(path) < min_length:
                min_length = len(path)
                min_path = path
        for node in min_path:
            print(f'({node[0]},{node[1]})')
    except:
        break

用时：40min