题解 | 迷宫问题

import sys

n = m = 0
index = 0
map = []
flag = []
for line in sys.stdin:
    a = line.split("\n")[0]
    if index == 0:
        aa = a.split(" ")
        n = int(aa[0])
        m = int(aa[1])
    else:
        map.append([int(_) for _ in a.split(" ")])
        flag.append([0 for _ in a.split(" ")])
    index += 1
#print(map)
#print(flag)

def dfs(x,y,history):
    #print(history)
    if not flag[x][y]:
        #history.append((x,y))
        flag[x][y]=1
    if x == len(map)-1 and y == len(map[0])-1:
        history.append((x,y))
        return
    if x + 1 <= len(map)-1 and not flag[x+1][y] and not map[x+1][y]:
        history.append((x,y))
        return dfs(x+1,y,history)
    elif x - 1 >= 0 and not flag[x-1][y] and not map[x-1][y]:
        history.append((x,y))
        return dfs(x-1,y,history)
    elif y + 1 <= len(map[0])-1 and not flag[x][y+1] and not map[x][y+1]:
        history.append((x,y))
        return dfs(x,y+1,history)
    elif y - 1 >= 0 and not flag[x][y-1] and not map[x][y-1]:
        history.append((x,y))
        return dfs(x,y-1,history)
    else:
        # 无路可走,开始回退上一个位置,history[-1]
        h = history.pop()
        #print(h)
        return dfs(h[0],h[1],history)
    

history = []
dfs(0,0,history)
for _ in history:
    print("(%s,%s)" % _)

找到能走的路径用dfs最快

如果是找最短那么就是bfs

dfs 就是无脑递归往下走,然后记录history 和flag 表示来时的路和已经走过的路,然后map 为 1 的是墙不能走

走过的路不能走

无路可走了 return history.pop() 再记录下已经走过这里了,那么最终只会剩下一条路,如果多条也是遇到第一条就结束.

bfs 则是把能走的都走一遍,然后把下次要走的加到队列中,遇到了结果了那么就记录下长度

也就是队列里面存的是三元组(x,y,已经走过的长度)

这样就比较方便了