题解 | dfs深度优先python3 解决经典#迷宫问题#

最近突击学习了一下dfs，代码按dfs模板写完，突然就跑出正确答案了。中间的递归思想感觉自己还是没学清楚。不过看了下其他题解，有很多写法没有运用到dfs的核心思想，好多还要判断上下左右有没有墙，然后再决定往哪个方向走（这一步应该交给代码自己遍历。本题可以参考leetcode 200 岛屿数量https://leetcode-cn.com/problems/number-of-islands/.

用深度优先，代码自己可以跑完所有含‘0’的路径，重点是如何返回到达goal的路径，并记录每次坐标。我们可以标记走过的map[x][y]=1，表示这个点已经访问了（建个墙，类似于leetcode200中“冲岛”处理）。这样操作后，当代码探索其中某一条路径时候不会走“回头路”（否则，会围着点不断打转）。同时将该点添加到路径route中。

然后应用回溯递归的思想，如果我们无法到达指定终点，则需要沿原路返回,再把标记过的路去掉 map[x][y]=0，route.pop(), 直到到达当初的分岔路口，进入下一次选择(这个过程有点像stack里的pop())。

如何知道该点是否到达goal呢？如果某个点，四周都是1（无法访问）说明“这条路”到头了，如果这个点坐标并不等于goal，那么返回 return，递归开始回退，沿“原路”返回，直到最近的一个分岔口，进入到另个方向的探索。

否则在刚进入 dfs 函数时就会在第一步的判断中打印出 route并且停止函数运行。

DFS搜索的本质就是递归回溯！！！

def dfs(i,j):
    dx = [0,0,-1,1]
    dy = [-1,1,0,0]
    if i == m-1 and j == n-1:
        for pos in route:
            print('('+str(pos[0])+','+str(pos[1])+')')
        return
    
    for k in range(4):
        x = i+dx[k]
        y = j+dy[k]
        if x>=0 and x<m and y>=0 and y<n and map1[x][y]==0:
            map1[x][y]=1
            route.append((x,y))
            dfs(x,y)
            map1[x][y]=0
            route.pop()
    else:
        return
            

while True:
    try:
        m,n = list(map(int,input().split()))
        map1=[]
        for i in range(m):
            s=list(map(int,input().split()))
            map1.append(s)
		// 初始值是（0，0）将其标记为已经访问
        route = [(0,0)]
        map1[0][0]=1
        dfs(0, 0)
        
    except:
        break