【题目来源】
【题目描述】
给定一个 N×M 方格的迷宫，迷宫里有 T 处障碍，障碍处不可通过。
在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。
给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。
【输入格式】
第一行为三个正整数 N,M,T，分别表示迷宫的长宽和障碍总数。
第二行为四个正整数 SX,SY,FX,FY。SX,SY 代表起点坐标，FX,FY 代表终点坐标。
接下来 T 行，每行两个正整数，表示障碍点的坐标。
【输出格式】
输出从起点坐标到终点坐标的方案总数
【输入样例】
2 2 1
1 1 2 2
1 2
【输出样例】
1
【数据范围】
对于 100% 的数据，1≤N,M≤5，1≤T≤10，1≤SX,FX≤N，1≤SY,FY≤M。
【算法分析】
● 迷宫问题是典型的 DFS 连通性应用问题。
● 迷宫可抽象为二维网格图，每个可行走格子视为图的节点，相邻可达格子之间构成连通关系。
● 利用 DFS 沿着网格上下左右四个方向逐层深入探索，通过边界条件、障碍物判定与访问标记数组进行剪枝，避免越界、重复走访与无效路径，同时借助回溯机制还原现场，继续尝试其他分支路径。整个过程依托图的连通性遍历思想，依靠 DFS 深入搜索、回溯试探的核心逻辑，完成从起点到终点的路径查找、可行域连通块统计等求解目标，是理解 DFS 连通遍历与回溯思想最经典的入门模型。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=6;
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
int maze[N][N];
bool st[N][N];
int n,m;
int sx,sy,ex,ey,cnt;void dfs(int x,int y) {if(x==ex && y==ey) {cnt++;return;}for(int k=0; k<4; k++) {int tx=x+dx[k];int ty=y+dy[k];if(tx>=1 && tx<=n && ty>=1 && ty<=m) {if(!maze[tx][ty] && !st[tx][ty]) {st[tx][ty]=true;dfs(tx,ty);st[tx][ty]=false;}}}return;
}int main () {int T;cin>>n>>m>>T;cin>>sx>>sy>>ex>>ey;maze[sx][sy]=true;while(T--) {int x,y;cin>>x>>y;maze[x][y]=true;}dfs(sx,sy);cout<<cnt<<endl;return 0;
}/*
in:
2 2 1
1 1 2 2
1 2out:
1
*/
【参考文献】