题解 | #迷宫问题#

回溯算法解析

dfs(grid,i,j,visited,paths)

1. 函数参数和返回值：

   1. 参数：i表示矩阵的行下标；j表示矩阵的列下标

   2. 返回值：该函数的主要目的是遍历矩阵并存储可行的路径，具体不需要返回任何值

2. 函数终止条件：什么时候我们希望继续搜索？什么时候希望终止搜索？

   1. 下标越界：如果 & 不满足，则说明下标越界，返回False终止深度搜索

   2. 重复访问：如果(i,j)已经被访问过，则我们在循环行走，返回False终止深度搜索

   3. 撞墙：如果grid[i][j]==1，则球撞墙，此路无法通行，返回False终止搜索

   4. 到达终点：如果 ，则球到达终点，收集该坐标，并且返回True终止搜索

3. 递归工作：

• 记录并存储当前访问的节点：visited[i][j]=True paths.append((i,j))
• 开始深度搜索。因为存在四个方向，所以分为四种情况，只需要任意一种情况能找到有效路径即可：
  • 向上搜索：dfs(grid,i-1,j,visited,paths)
  • 向下搜索：dfs(grid,i+1,j,visited,paths)
  • 向左搜索：dfs(grid,i,j-1,visited,paths)
  • 向右搜索：dfs(grid,i,j+1,visited,paths)
• 如果以某个点(i,j)为起点启动的深度搜索在四个方向都无法找到任何有效路径，即进入死胡同，则此路无解，我们需要回溯并尝试其他路径：paths.pop()

def maze(grid):
    visited = [[False]*n for _ in range(m)]
    paths = []

    def dfs(i,j):
        if not 0<=i<m or not 0<=j<n or visited[i][j] or grid[i][j]==1: return False
        if i==m-1 and j==n-1:
            paths.append((i,j))
            return True

        visited[i][j] = True
        paths.append((i,j))

        if dfs(i+1,j) or dfs(i-1,j) or dfs(i,j+1) or dfs(i,j-1):
            return True
        paths.pop()

    dfs(0,0)
    return paths

m,n = map(int,input().split())
grid = []
for i in range(m):
    grid.append((list(map(int,input().split()))))
for path in maze(grid):
    print("({},{})".format(path[0],path[1]))