1 条题解

  • 0
    @ 2025-7-9 19:25:26

    #include #include using namespace std;

    int N, M, T; int sx, sy, fx, fy; int grid[6][6]; // 标记矩阵:0-可走且未访问,1-障碍,2-已访问 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向 int count = 0; // 记录路径总数

    void dfs(int x, int y) { // 若到达终点,路径数加1 if (x == fx && y == fy) { count++; return; }

    // 尝试四个方向的移动
    for (int i = 0; i < 4; i++) {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];
        
        // 检查新位置是否合法(在迷宫内、非障碍、未访问)
        if (nx >= 1 && nx <= N && ny >= 1 && ny <= M && grid[nx][ny] == 0) {
            grid[nx][ny] = 2; // 标记为已访问
            dfs(nx, ny);      // 递归探索
            grid[nx][ny] = 0; // 回溯,取消标记
        }
    }
    

    }

    int main() { cin >> N >> M >> T; cin >> sx >> sy >> fx >> fy;

    // 初始化标记矩阵,所有位置初始为可走(0)
    memset(grid, 0, sizeof(grid));
    
    // 标记障碍位置
    for (int i = 0; i < T; i++) {
        int x, y;
        cin >> x >> y;
        grid[x][y] = 1;
    }
    
    // 标记起点为已访问
    grid[sx][sy] = 2;
    
    // 从起点开始DFS
    dfs(sx, sy);
    
    // 输出路径总数
    cout << count << endl;
    
    return 0;
    

    }

    • 1

    信息

    ID
    76
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    39
    已通过
    18
    上传者