题目描述

xca最近被走迷宫问题折磨的不行，他现在有这样一个走迷宫的问题，给定一个n∗m方格的迷宫，迷宫里有t处障碍，障碍处不可通过。现在给定起点坐标和终点坐标，要求每次只能在迷宫中走一步，且迷宫中移动有上下左右四种方式。数据保证起点和终点上没有障碍，且至少有一条路径。问:
有多少种从起点坐标到终点坐标的方案。

输入格式
第一行n、m和t(n为行，m为列，t为障碍总数)
第二行起点坐标(sx,sy)，终点坐标(fx,fy)
接下来t行，每行为障碍点的坐标(x, y)

输出格式
从起点坐标到终点坐标的方案总数

输入样例

2 2 1
1 1 
2 2
1 2

输出样例

1

DFS深度递归求解

思路

① 设置地图map[N][M], 其中m[i][j]为0时表示可以通行, m[i][j]为1时表示不可以通行, 再设置exist[N][M]存储已经访问的点, 访问时标记为1, 未访问时标记为0
② 从起始位置(sx, sy)开始遍历上下左右四个方向移动, 移动后的点判断是否出界和被访问过, 遍历下一点(a,b)进行递归要标记当前点(x, y)为已经遍历, 当回溯到当前层是要恢复当前的(x,y)为没有遍历
③ 递归终止条件x == fx && y == fy

参考文献

蛇形矩阵:https://www.acwing.com/activity/content/code/content/1940867/

C++ 代码

#include <iostream>

using  namespace std;
const int N = 100;
int map[N][N];  // 表示地图， 0表示没有障碍 
int exist[N][N];  // 标记已经访问 
int cnt = 0;  // 统计路径数 
int sx, sy, fx, fy;  // (sx,sy)起始点 （fx,fy）终点
int n, m, t;  // n为行, m为列, t为障碍数 

void dfs(int x, int y){
    if (x == fx && y == fy){  // 递归终止
        cnt ++;
        return;  // 回溯到上一层 
    }
    int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 0; i < 4; i ++){
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m || exist[a][b] || map[a][b])
            continue;
        exist[x][y] = 1;  // 表示（x, y）已经走过
        dfs(a, b); 
        exist[x][y] = 0; // 恢复当前的x,y为没有遍历 
    } 
}
int main(){
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;  

    while(t --){
        int x, y;
        cin >> x >> y;
        map[x][y] = 1;  // 1 表示有障碍 
    } 
    dfs(sx, sy);
    cout << cnt << endl;

    return 0;
}

${如果有更好的思路, 还望dalao评论区告知,orz}$