题解 | 迷宫问题

参考的解题区的思路。

1、遍历图总所有能遍历的点，直到到达目的点。

2、输出轨迹坐标。

h, w = map(int, input().split())
matrix = [input().split() for _ in range(h)]
#格式化输入

def dfs(x: int, y: int, h: int, w: int, ans: list, matrix: list):
    if x == h - 1 and y == w - 1:#到达目的点
        [print(f"({k},{v})") for k, v in ans]
    if x + 1 < h and matrix[x + 1][y] == "0" and (x + 1, y) not in ans:
        dfs(x + 1, y, h, w, ans + [(x + 1, y)], matrix)#向右
    if y + 1 < w and matrix[x][y + 1] == "0" and (x, y + 1) not in ans:
        dfs(x, y + 1, h, w, ans + [(x, y + 1)], matrix)#向下
    if x - 1 >= 0 and matrix[x - 1][y] == "0" and (x - 1, y) not in ans:
        dfs(x - 1, y, h, w, ans + [(x - 1, y)], matrix)#向左
    if y - 1 >= 0 and matrix[x][y - 1] == "0" and (x, y - 1) not in ans:
        dfs(x, y - 1, h, w, ans + [(x, y - 1)], matrix)#向上
#bfs+dfs，遍历图中所有能遍历的点，直到找到目标点

dfs(0, 0, h, w, [(0, 0)], matrix)
#执行函数