全部评论 2

  • 让我康康

    #include <cstdio>
    #include <cmath>
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    int n, m, t, sx, sy, fx, fy, cnt = 0;
    int mp[10][10] = {0}; 
    bool vis[10][10] = {0};
    inline int manhattan(int x, int y) {
        return abs(x - fx) + abs(y - fy);
    }
    inline bool check(int nx, int ny) {
        return nx >= 1 && nx <= n && ny >= 1 && ny <= m 
               && !vis[nx][ny] && mp[nx][ny] != 1;
    }
    void dfs(int x, int y, int steps) {
        if (x == fx && y == fy) {
            cnt++;
            return;
        }
        int min_remaining = manhattan(x, y);
        int max_possible = (n*m - t) - steps;  
        if (min_remaining > max_possible) {
            return;
        }
        
        vis[x][y] = 1; 
        
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (check(nx, ny)) {
                dfs(nx, ny, steps + 1); 
            }
        }
        
        vis[x][y] = 0;
    }
    
    int main() {
        scanf("%d%d%d", &n, &m, &t);
        scanf("%d%d%d%d", &sx, &sy, &fx, &fy);
        if (mp[sx][sy] == 1 || mp[fx][fy] == 1) {
            printf("0");
            return 0;
        }
        for (int i = 0, x, y; i < t; i++) {
            scanf("%d%d", &x, &y);
            mp[x][y] = 1;
        }
        dfs(sx, sy, 1);
        printf("%d", cnt);
        return 0;
    }
    

    17小时前 来自 广东

    0
  • 2025-04-21 来自 浙江

    0

热门讨论