HJ148 迷宫寻路

题目描述

旺仔哥哥被困在一个 n×m 的矩形迷宫里。每个格子要么是空地（用符号 . 表示），要么是墙（用符号 # 表示）。旺仔哥哥只能从一个空地移动到其上下左右相邻的空地。

已知旺仔哥哥的起点为左上角 (1,1)，终点为右下角 (n,m)。请判断他是否能够到达终点。

保证起点和终点均为空地。

解题思路

这是一道典型的迷宫寻路问题，使用深度优先搜索(DFS)即可解决。

核心思路

1. 从起点开始DFS遍历：每次尝试向四个方向（上下左右）移动
2. 边界检查：确保不越界（0 ≤ x < n，0 ≤ y < m）
3. 合法性检查：只能移动到空地（.）且未访问过的格子
4. 标记已访问：使用 visited 数组避免重复访问，防止死循环
5. 终止条件：到达终点 (n-1, m-1) 时返回成功

代码实现

n, m = map(int, input().split())
s = [list(input()) for _ in range(n)]

visited = [[False] * m for _ in range(n)]

def dfs(x, y):
    if x == n - 1 and y == m - 1:
        return True
    visited[x][y] = True
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and s[nx][ny] == '.':
            if dfs(nx, ny):
                return True
    return False

print("Yes" if dfs(0, 0) else "No")

代码解析

核心函数 dfs(x, y)

参数	含义
x, y	当前位置的坐标

算法流程

dfs(0, 0)
    ↓
    标记 (0,0) 为已访问
    ↓
    尝试四个方向
    ↓
    ┌───┴───┬───┴───┐
    ↓       ↓       ↓       ↓
   向右    向左    向下    向上
   (0,1)  越界    (1,0)   越界
    ↓       ↓       ↓       ↓
   继续DFS  跳过   继续DFS  跳过

关键点

1. 方向数组：[(0, 1), (0, -1), (1, 0), (-1, 0)] 分别代表右、左、下、上
2. 访问标记：进入格子时立即标记，防止后续重复访问
3. 早期返回：一旦找到通往终点的路径，立即返回 True，不再搜索其他路径

示例演示

输入：

3 5
.##.#
.#...
...#.

搜索过程：

(0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (1,2) → (1,3) → (1,4) → (2,4) ✓

输出：Yes

复杂度分析

• 时间复杂度：O(n × m) - 最坏情况下遍历所有格子
• 空间复杂度：O(n × m) - visited 数组 + 递归栈深度

优化建议

1. BFS解法：若需要求最短路径，可用 BFS 并记录距离
2. 路径记录：可用 path 数组记录来路，输出具体路径
3. 原地标记：可直接将访问过的 . 改为 #，省去 visited 数组