【题目来源】
洛谷：P1605 迷宫 - 洛谷
【题目描述】
给定一个 \(N \times M\) 方格的迷宫，迷宫里有 \(T\) 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
【输入】
第一行为三个正整数 \(N,M,T\)，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 \(SX,SY,FX,FY\)，\(SX,SY\) 代表起点坐标，\(FX,FY\) 代表终点坐标。
接下来 \(T\) 行，每行两个正整数，表示障碍点的坐标。
【输出】
输出从起点坐标到终点坐标的方案总数。
【输入样例】
2 2 1
1 1 2 2
1 2
【输出样例】
1
【解题思路】
【算法标签】
《洛谷 P1605 迷宫》 #搜索# #递推# #枚举# #USACO#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n, m: 网格的行数和列数
// t: 障碍物的数量
// sx, sy: 起点坐标
// fx, fy: 终点坐标
// a[10][10]: 网格状态（1表示可通行，0表示障碍或已访问）
// x, y: 临时坐标变量
// ans: 记录从起点到终点的路径总数
int n, m, t, sx, sy, fx, fy, a[10][10], x, y, ans = 0;// 方向数组：上、下、左、右
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};/*** 深度优先搜索函数* @param x 当前行坐标* @param y 当前列坐标*/
void dfs(int x, int y)
{int xx, yy;// 如果到达终点，增加路径计数并返回if (x == fx && y == fy){ans++;return;}// 尝试四个移动方向for (int i = 0; i <= 3; i++){xx = x + dx[i];yy = y + dy[i];// 检查新位置是否合法且可通行if (xx > 0 && xx <= n && yy > 0 && yy <= m && a[xx][yy] == 1){a[xx][yy] = 0; // 标记为已访问dfs(xx, yy); // 递归搜索a[xx][yy] = 1; // 回溯，恢复可通行状态}}
}int main()
{// 输入网格大小和障碍物数量cin >> n >> m >> t;// 输入起点和终点坐标cin >> sx >> sy >> fx >> fy;// 初始化网格为全部可通行for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){a[i][j] = 1;}}// 设置障碍物位置for (int i = 1; i <= t; i++){cin >> x >> y;a[x][y] = 0;}// 标记起点为已访问a[sx][sy] = 0;// 开始深度优先搜索dfs(sx, sy);// 输出路径总数cout << ans;return 0;
}
【运行结果】
2 2 1
1 1 2 2
1 2
1