题解 |DFS #迷宫问题# python 带注释

while True:
    try:
        m,n=list(map(int , input().split()))
        maze=[]
        for _ in range(m):
            maze.append(list(map(int,input().split())))

            
            
        def walk(i, j, pos=[(0, 0)]):
            if j+1 < n and maze[i][j+1] == 0: # 向右
                if (i, j+1) not in pos:
                    walk(i, j+1, pos + [(i, j+1)])
            if j-1 >= 0 and maze[i][j-1] == 0: # 向左
                if (i, j-1) not in pos:
                    walk(i, j-1, pos + [(i, j-1)])
            if i+1 < m and maze[i+1][j] == 0: # 向下
                if (i+1, j) not in pos:
                    walk(i+1, j, pos + [(i+1, j)])
            if i-1 >= 0 and maze[i-1][j] == 0: # 向上
                if (i-1, j) not in pos:
                    walk(i-1, j, pos + [(i-1, j)])
            if (i, j) == (m-1, n-1): # 到达出口
                for p in pos:
                    print('(' + str(p[0]) + ',' + str(p[1]) + ')')
                    
        walk(0, 0)
    except:
        break

while True:
    try:
        m, n = list(map(int, input().split()))  # 读取输入的两个整数 m 和 n，表示迷宫的行数和列数
        maze = []  # 创建一个空列表来存储迷宫的数据
        for _ in range(m):
            maze.append(list(map(int, input().split())))  # 逐行读取迷宫的数据，并将其添加到 maze 列表中

        def walk(i, j, pos=[(0, 0)]):  # 定义一个递归函数 walk，用于遍历迷宫
            if j + 1 < n and maze[i][j + 1] == 0:  # 如果当前位置的右侧是可通行的（值为0），则向右移动
                if (i, j + 1) not in pos:  # 如果该位置未被访问过，则继续递归调用 walk 函数
                    walk(i, j + 1, pos + [(i, j + 1)])
            if j - 1 >= 0 and maze[i][j - 1] == 0:  # 如果当前位置的左侧是可通行的（值为0），则向左移动
                if (i, j - 1) not in pos:  # 如果该位置未被访问过，则继续递归调用 walk 函数
                    walk(i, j - 1, pos + [(i, j - 1)])
            if i + 1 < m and maze[i + 1][j] == 0:  # 如果当前位置的下方是可通行的（值为0），则向下移动
                if (i + 1, j) not in pos:  # 如果该位置未被访问过，则继续递归调用 walk 函数
                    walk(i + 1, j, pos + [(i + 1, j)])
            if i - 1 >= 0 and maze[i - 1][j] == 0:  # 如果当前位置的上方是可通行的（值为0），则向上移动
                if (i - 1, j) not in pos:  # 如果该位置未被访问过，则继续递归调用 walk 函数
                    walk(i - 1, j, pos + [(i - 1, j)])
            if (i, j) == (m - 1, n - 1):  # 如果当前位置是迷宫的出口，则打印路径
                for p in pos:
                    print('(' + str(p[0]) + ',' + str(p[1]) + ')')

        walk(0, 0)  # 从起点开始遍历迷宫
    except:
        break  # 如果发生异常，则退出循环

**这段代码使用的是深度优先搜索（DFS）算法**。

在给出的代码中，`walk` 函数通过递归的方式访问迷宫中的每个位置。它首先尝试向下、向右、向左和向上四个方向移动，如果某个方向可通行且未被访问过，则进行递归调用，继续探索该方向的路径。这种先探索一个方向直到无法继续为止，然后回溯到上一个分叉点再探索另一个方向的过程，是典型的深度优先搜索的行为。

深度优先搜索（DFS）的特点在于它使用栈（在递归实现中，系统调用栈充当这一角色）来实现搜索过程。它会沿着一条路径深入直到无法继续，然后回溯到上一个节点，寻找另一条可能的路径。这种方式保证了搜索能够触及所有可能的路径，直到找到目标或者所有的节点都被访问过。

相比之下，广度优先搜索（BFS）则是逐层进行的，它使用队列来存储每一层的节点，并按层次顺序访问这些节点。BFS通常用于寻找最短路径问题，因为它按照从起点开始的距离顺序来访问节点。

总结来说，代码中使用了DFS算法来进行迷宫遍历，这体现在递归探索各个方向直到到达终点或所有可通行的路径都被访问过的搜索策略上。