P1605 迷宫
题目描述
给定一个 \(N \times M\) 方格的迷宫，迷宫里有 \(T\) 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
输入格式
第一行为三个正整数 \(N,M,T\)，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 \(SX,SY,FX,FY\)。\(SX,SY\) 代表起点坐标，\(FX,FY\) 代表终点坐标。
接下来 \(T\) 行，每行两个正整数，表示障碍点的坐标。
输出格式
输出从起点坐标到终点坐标的方案总数。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 \(100\%\) 的数据，\(1 \le N,M \le 5\)，\(1 \le T \le 10\)，\(1 \le SX,FX \le N\)，\(1 \le SY,FY \le M\)。
Tip
📌 题目分析
给定数据：
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么使用 DFS 而不是 BFS？
这是迷宫题里最容易搞混的知识点： * 如果题目问的是“最短路径是多少”或者“最少走几步”，我们首选 BFS (广度优先搜索)。 * 但这道题问的是“一共有多少种走法”，要求我们找出所有能到达终点的路径。在极端小的数据范围（最多 25 个格子）下，通过 DFS (深度优先搜索) 一条路走到黑，撞墙再退回来换条路走（回溯），是标准的解法。
2️⃣ 核心回溯逻辑（保护与恢复现场）
所谓回溯，就是“试错并退回”。
当我们走到坐标 (x, y) 时：
1. 标记：我们把这个格子标记为“已走过”，防止在这一条路径里绕圈子死循环。
2. 深入：尝试向上下左右四个方向走。
3. 撤销：当我们把这四个方向都试完，准备退回到上一步时，必须把 (x, y) 的“已走过”标记擦除。因为在这个大格子里，另一条完全不同的路径可能还会经过这里。
3️⃣ 边界与障碍物处理
开一个二维数组 maze 记录障碍物（如 1 表示障碍，0 表示空地）。
开一个二维布尔数组 vis 记录当前路径是否走过。
每次向四个方向走之前，做一次安全检查：
不能越界、不能是障碍物、不能是当前路径已经走过的格子。
4️⃣ 时间复杂度
在没有任何剪枝的情况下，每次最多有 3 个方向可以走（除了来的方向）。最坏的时间复杂度接近指数级： \(O(3^{N \times M})\) 但在 \(N, M \le 5\) 的超小数据范围内，运算量极小，绝对可以在 1 秒内跑完。
💻 C++代码
#include <iostream>
using namespace std;
int n, m, t;
int sx, sy, fx, fy;
int ans = 0;
int maze[10][10]; // 0 表示空地，1 表示障碍
bool vis[10][10]; // true 表示当前路径已访问过该点
// 方向数组：上下左右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
void dfs(int x, int y) {
// 边界条件：到达终点
if (x == fx && y == fy) {
ans++; // 方案数加一
return;
}
// 枚举四个方向
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 检查：1. 是否越界 2. 是否是障碍 3. 是否已访问
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && maze[nx][ny] == 0 && !vis[nx][ny]) {
vis[nx][ny] = true; // 【标记】走到新格子，保护现场
dfs(nx, ny); // 【深入】继续往下搜
vis[nx][ny] = false; // 【回溯】退回来时，恢复现场，供其他路径使用
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
// 读入障碍物坐标
for (int i = 0; i < t; i++) {
int r, c;
cin >> r >> c;
maze[r][c] = 1; // 标记为障碍物
}
// !!! 极其重要：起点在出发前必须被标记为已访问
vis[sx][sy] = true;
// 从起点开始搜索
dfs(sx, sy);
cout << ans << "\n";
return 0;
}
⚠️ 易错点
❌ 1. 忘记标记起点
这是无数人吃过亏的地方：
如果没有这一句，你在搜索的过程中，很可能会从起点的旁边又走回到起点，导致起点被经过了两次，最终答案会比正确答案偏大。
❌ 2. 回溯漏掉恢复现场
如果忘记写 vis[nx][ny] = false;，那么你的 DFS 就不再是找“所有”路径，而是类似于涂色游戏，走过的地方就永远被堵死了。这会导致最终搜出来的路径数量极少。
❌ 3. 数组越界导致 RE
题目的行列是从 1 到 \(N\) 和 \(M\)。所以在判断边界时，必须是 >= 1 和 <= n。如果习惯了从 0 开始遍历的写法，直接写成 >= 0 会导致访问到矩阵外层的默认零值，从而产生逻辑错误甚至越界崩溃。
🚀 一句话总结
🔥 补充：硬核知识点
搜索算法的核心哲学：状态树的遍历
很多初学者觉得 DFS 和回溯法很抽象。其实你可以把迷宫想象成一棵巨大的树：
* 树根就是起点 (SX, SY)。
* 树的枝干就是你在每个格子上做出的四个方向的选择。
* 树的叶子要么是死胡同（撞墙/越界），要么就是终点 (FX, FY)。
在这个视角下： * DFS（深度优先） 是一只老鼠，它顺着一根树枝一直爬，要么爬到终点（答案+1），要么爬到尽头死胡同。无论如何它都会原路退回（也就是所谓的回溯），去爬下一根树枝。所以它能极其方便地统计出共有多少条路。 * BFS（广度优先） 则像是一滴水滴在迷宫起点，它以涟漪的形态同时向四周扩散。最先触碰到终点的那一圈波纹，必定就是最短的一条路。但它很难搞清楚到底有多少种独立的波纹轨迹（因为波纹在扩散时融合了）。
理解了老鼠（DFS）与水波（BFS）的意象，你就能在看到题目问“几条路”还是“几步路”时，瞬间选出最正确的算法武器！