B3625 迷宫寻路
题目描述
机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 \(n\times m\) 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。
机器猫初始时位于 \((1, 1)\) 的位置，问能否走到 \((n, m)\) 位置。
输入格式
第一行，两个正整数 \(n,m\)。
接下来 \(n\) 行，输入这个迷宫。每行输入一个长为 \(m\) 的字符串，# 表示墙，. 表示空地。
输出格式
仅一行，一个字符串。如果机器猫能走到 \((n, m)\)，则输出 Yes；否则输出 No。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
样例解释
路线如下：\((1,1)\to (2,1) \to (3,1) \to (3,2)\to (3,3) \to (2, 3) \to (2, 4) \to (2, 5) \to (3, 5)\)
数据规模与约定
对于 \(100\%\) 的数据，保证 \(1 \leq n, m \leq 100\)，且 \((1,1)\) 和 \((n, m)\) 均为空地。
Tip
📌 题目分析
给定数据：
问机器猫能否通过上下左右移动，从起点成功走到终点。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么使用搜索算法
题目只问“能不能走到”，也就是探究起点和终点是否在同一个“连通块”内。 这就像走实体迷宫，我们需要一种策略来穷举所有的分岔路口： * DFS（深度优先）：一条路走到黑，撞墙或者走进死胡同了，再退回到上一个路口换一条路继续走。 * BFS（广度优先）：像水波一样向外扩散，同时探索周围一圈的格子。
对于仅判断连通性的问题，两者皆可，这里我们使用代码量更短、逻辑更直观的 DFS。
2️⃣ 核心搜索逻辑
从坐标 (1, 1) 开始启动 DFS：
1. 检查当前所在的坐标是否就是终点 (n, m)，如果是，说明能走到，直接记录答案并结束。
2. 将当前坐标标记为“已访问”，防止等下走了一圈又绕回来，导致无限死循环。
3. 利用方向数组 dx 和 dy，向上下左右四个方向试探。
4. 只要新坐标在地图范围内、是空地 .、并且之前没走过，就递归调用 DFS 继续深入。
3️⃣ 与上一道题（P1605 迷宫）的区别
在上一道求“总方案数”的题目中，我们在回溯时必须恢复现场（把已访问标记改回未访问），因为我们需要穷举所有可能的路径。 但在这道题中，我们只需要找一条路，并且只关心“能不能到达”。 如果一条路被证明是死胡同退回来了，其他路径就算再经过这里，也同样是死胡同。所以在这道题里，走过的格子绝对不需要恢复现场，这能极大缩减运行时间！
4️⃣ 时间复杂度
由于我们标记了已访问的格子且不恢复现场，每个格子最多只会被访问一次。
最大 \(100 \times 100 = 10000\) 次操作，耗时接近 0 毫秒，极度安全。
💻 C++代码
#include <iostream>
using namespace std;
int n, m;
char maze[105][105]; // 存储迷宫地图
bool vis[105][105]; // 标记是否走过
bool found_path = false; // 记录是否找到终点
// 方向数组：上下左右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
// 1. 如果已经找到了，或者越界，直接剪枝退出
if (found_path) return;
// 2. 检查是否到达终点
if (x == n && y == m) {
found_path = true;
return;
}
// 3. 标记当前格子为已走过 (!!! 注意：不需要恢复现场 !!!)
vis[x][y] = true;
// 4. 枚举四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 检查边界条件、是否是空地、是否未访问
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && maze[nx][ny] == '.' && !vis[nx][ny]) {
dfs(nx, ny);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
// 从 1 开始读取地图，保证坐标体系与题目 (1,1) -> (n,m) 完全一致
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> maze[i][j];
}
}
// 从起点启动搜索
dfs(1, 1);
// 输出结果
if (found_path) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 死循环导致爆栈 (MLE / RE / TLE)
如果不使用 vis 数组标记，或者把条件写错了，DFS 就会在两个相邻的空地之间反复横跳（A 走向 B，B 走向 A），瞬间产生上万层的递归，直接引发 Stack Overflow 导致程序崩溃。
❌ 2. 坐标系对齐问题
迷宫类题目最怕的就是越界或者错位。
如果习惯了数组从 0 开始存（比如用 string 读取），那么起点其实是 (0, 0)，终点是 (n-1, m-1)。代码中所有的边界判断也要改成 0 到 n-1。
为了不绕晕自己，强烈建议就像上面代码一样，统一使用从 1 开始的二维 char 数组，做到题干怎么说，代码就怎么写。
❌ 3. 错误地恢复了现场
如果你习惯性地在这道题里加上了 vis[nx][ny] = false;，虽然答案不会错，但它会从 \(O(N \times M)\) 的复杂度退化成指数级。如果测试点设计得非常“空旷”，你的代码会因为尝试了无数条不同的弯路而直接超时（TLE）。
🚀 一句话总结
🔥 补充
硬核知识点：DFS 与 BFS 在网格图中的抉择
虽然这道题用 DFS 可以极简 AC，但在实际的算法竞赛和面试中，关于网格迷宫问题，老手通常会优先选择 BFS（利用队列）。
原因在于 DFS 的递归深度陷阱：
* 每次 DFS 调用都会在内存的“栈区”分配空间。普通的评测机栈空间可能只有几兆。
* 如果这是一个 \(1000 \times 1000\) 的超大空旷迷宫，DFS 就像一条蛇一样蜿蜒前行，最坏情况下会达到 \(1,000,000\) 层的递归深度，必定会导致段错误 (Segmentation Fault / RE)。
* 而 BFS 使用的是自定义在堆区的 std::queue，空间极大，绝不会爆栈。
* 并且，如果在没有权重的网格图中，题目把问题从“能不能到”改成了“最少走几步到”，那么 DFS 彻底歇菜，BFS 则能凭借其波纹扩散的特性，精准给出最短步数！