A0512 迷宫(求方案)

#include <bits/stdc++.h>
using namespace std;

int n, m, T;
int sx, sy, fx, fy;
vector<vector<int>> g;
bool vis[8][8];
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

long long dfs(int x, int y) {
    if (x == fx && y == fy) return 1;      // 到达终点，算一种方案
    vis[x][y] = true;
    long long cnt = 0;
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (g[nx][ny] || vis[nx][ny]) continue;   // 障碍或已经走过
        cnt += dfs(nx, ny);
    }
    vis[x][y] = false;                      // 回溯：当前格子可以留给别的路径
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> T;
    cin >> sx >> sy >> fx >> fy;
    g.assign(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i < T; i++) {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;                        // 障碍
    }

    cout << dfs(sx, sy) << '\n';
    return 0;
}