今天做迷宫https://www.luogu.com.cn/problem/P1605

迷宫

题目描述

给定一个 $N \times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。 在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。 给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。 第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。 接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。

输出格式

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

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #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$。

cpp
#include <iostream>
using namespace std;

const int MAXN = 5;
const int MAXM = 5;

int N, M, T;
int SX, SY, FX, FY;
bool maze[MAXN + 1][MAXM + 1]; // false 表示可以通过，true 表示障碍
bool visited[MAXN + 1][MAXM + 1]; // 记录是否访问过

int dx[] = {0, 0, 1, -1}; // 右、左、下、上
int dy[] = {1, -1, 0, 0};

int dfs(int x, int y) {
    if (x == FX && y == FY) {
        return 1; // 到达终点，返回1表示找到一条路径
    }

    visited[x][y] = true; // 标记当前位置为已访问
    int count = 0;

    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] && !visited[nx][ny]) {
            count += dfs(nx, ny); // 递归搜索下一个位置
        }
    }

    visited[x][y] = false; // 回溯，取消当前位置的访问标记
    return count;
}

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) {
            maze[i][j] = false;
            visited[i][j] = false;
        }
    }

    // 读取障碍点
    for (int i = 0; i < T; ++i) {
        int x, y;
        cin >> x >> y;
        maze[x][y] = true;
    }

    // 从起点开始DFS
    int result = dfs(SX, SY);

    cout << result << endl;

    return 0;
}