Python小练习系列 Vol.4：迷宫寻路（回溯 + DFS）

🧠 Python小练习系列 Vol.4：迷宫寻路（回溯 + DFS）

🚪 本期我们将探索一个二维世界，借助回溯算法帮助角色走出迷宫！这是学习路径搜索类题目的经典案例。

---

🧩 一、题目描述

给定一个二维迷宫地图（由 0 和 1 组成），其中 0 表示可以通行，1 表示障碍。

请找出从起点 (0, 0) 到终点 (n-1, m-1) 的一条可行路径（若存在），并打印路径坐标。

示例输入：

maze = [[0, 1, 0, 0],[0, 0, 0, 1],[1, 1, 0, 1],[0, 0, 0, 0]
]

输出：

路径：[ (0,0) → (1,0) → (1,1) → (1,2) → (2,2) → (3,2) → (3,3) ]

---

🧠 二、解题思路

我们用回溯（DFS）方法遍历迷宫中的所有可能路径，尝试从当前位置向四个方向走，遇到合法路径则继续递归。

注意点：

• 防止越界
• 避免走回头路（设置 visited 标记）
• 如果走到终点，记录路径并返回

---

👨‍💻 三、Python代码实现

def find_path(maze):n, m = len(maze), len(maze[0])path = []visited = [[False]*m for _ in range(n)]def dfs(x, y):if not (0 <= x < n and 0 <= y < m):return Falseif maze[x][y] == 1 or visited[x][y]:return Falsepath.append((x, y))visited[x][y] = Trueif x == n - 1 and y == m - 1:return Truefor dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:  # 右下左上if dfs(x + dx, y + dy):return Truepath.pop()return Falseif dfs(0, 0):return pathelse:return None

---

📌 四、运行示例

maze = [[0, 1, 0, 0],[0, 0, 0, 1],[1, 1, 0, 1],[0, 0, 0, 0]
]res = find_path(maze)
print("路径：" + " → ".join(map(str, res)) if res else "无解")

---

🔎 五、思维总结

关键点	说明
状态记录	使用 visited 避免重复走
回溯动作	若走不通，撤回上一步 path
终止条件	到达终点 (n-1, m-1)

---

💡 六、进阶拓展

• 🚀 输出所有可行路径而不是第一条（稍作修改）
• 🌟 找最短路径（可改用 BFS）
• 🧱 让迷宫更复杂：加上传送门、陷阱等逻辑

---

❤️ 结语

回溯不仅能解谜题，还能帮你拓展逻辑思维边界。走迷宫就是算法世界的冒险启程！

📌 下一期预告：数独求解（经典回溯 + 剪枝）

---

👉 点个赞 👍 + 收藏 🌟，我们下期再见！