题目

题目描述

  1. 房间由 X * Y 的方格组成，例如下图为 6 * 4 的大小。每一个方格以坐标 (x，y) 描述。

  2. 机器人固定从方格 (0，0) 出发，只能向东或者向北前进。出口固定为房间的最东北角，如下图的方格 (5，3)。用例保证机器人可以从入口走到出口。

  3. 房间有些方格是墙壁，如 (4，1)，机器人不能经过那儿。

  4. 有些地方是一旦到达就无法走到出口的，如标记为 B 的方格，称之为陷阱方格。

  5. 有些地方是机器人无法到达的的，如标记为 A 的方格，称之为不可达方格，不可达方格不包括墙壁所在的位置。

  6. 如下示例图中，陷阱方格有 2 个，不可达方格有 3 个。

  7. 请为该机器人实现路径规划功能: 给定房间大小、墙壁位置，请计算出陷阱方格与不可达方格分别有多少个。

输入描述

  1. 第一行为房间的 X 和 Y (0 < X，Y = 1000)

  2. 第二行为房间中墙壁的个数 N (0 <= N < X*Y)

  3. 接着下面会有 N 行墙壁的坐标
    同一行中如果有多个数据以一个空格隔开，用例保证所有的输入数据均合法。 (结尾不带回车换行)

输出描述

陷阱方格与不可达方格数量，两个信息在一行中输出，以一个空格隔开。(结尾不带回车换行)

示例1

输入：

6 4
5
0 2
1 2
2 2
4 1
5 1

输出：

2 3

示例2

输入：

6 4
4
2 0
2 1
3 0
3 1

输出：

0 4

解题思路

该题型为迷宫/连通性 + 条件限制（单向可达性）。

两次 BFS。

第一次 BFS：起点 → 所有能走到的点，从 (0,0) 进行 BFS（方向仅向右和向上）：

  • 得到 visitedFromStart[x][y] = true

  • 所有没被访问到、又不是墙的格子 ⇒ 不可达方格 A。

第二次 BFS：反向可达性（终点往回走）。

机器人只能走 东、北（右、上）。反向 BFS 则是 从终点走 西、南（左、下）。

从 (Xmax, Ymax) 做 BFS：

  • 得到 canReachEnd[x][y] = true

这样就能判断哪些点能够最终走到终点。

陷阱方格 = 从起点能到，但从该点无法到达出口

即：visitedFromStart[x][y] == true && canReachEnd[x][y] == false

不可达方格 = 从起点不能到达 & 不是墙

即：visitedFromStart[x][y] == false && isWall[x][y] == false

代码

public class RobotWalkingTheMaze {

    public void solution(int x, int y, int[][] walls) {
        // 墙初始化
        boolean[][] isWall = new boolean[x][y];
        for (int[] wall : walls) {
            isWall[wall[0]][wall[1]] = true;
        }
        if (isWall[0][0] || isWall[x-1][y-1]) {
            System.out.println("0 0");
            return;
        }
        // 起点开始bfs
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {0, 0});
        int[][] dirsFromStart = {{1, 0}, {0, 1}};
        boolean[][] visitedFromStart = new boolean[x][y];
        visitedFromStart[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] dir : dirsFromStart) {
                int nx = dir[0] + cur[0];
                int ny = dir[1] + cur[1];
                if (nx >= 0 && nx < x && ny >= 0 && ny < y && !isWall[nx][ny] && !visitedFromStart[nx][ny]) {
                    q.offer(new int[] {nx, ny});
                    visitedFromStart[nx][ny] = true;
                }
            }
        }

        // 终点开始bfs
        q.clear();
        q.offer(new int[] {x - 1, y - 1});
        int[][] dirsFromEnd = {{-1, 0}, {0, -1}};
        boolean[][] canReachEnd = new boolean[x][y];
        canReachEnd[x-1][y-1] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] dir : dirsFromEnd) {
                int nx = dir[0] + cur[0];
                int ny = dir[1] + cur[1];
                if (nx >= 0 && nx < x && ny >= 0 && ny < y && !isWall[nx][ny] && !canReachEnd[nx][ny]) {
                    q.offer(new int[] {nx, ny});
                    canReachEnd[nx][ny] = true;
                }
            }
        }

        // 计算陷阱方块和不可达方块
        int trap = 0;
        int cantReach = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (!visitedFromStart[i][j] && !isWall[i][j]) {
                    cantReach++;
                }
                if (visitedFromStart[i][j] && !canReachEnd[i][j]) {
                    trap++;
                }
            }
        }
        System.out.print(trap + " " + cantReach);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        sc.nextLine();
        int N = sc.nextInt();
        sc.nextLine();
        int[][] walls = new int[N][2];
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            String[] xy = line.split(" ");
            int wx = Integer.parseInt(xy[0]);
            int wy = Integer.parseInt(xy[1]);
            walls[i][0] = wx;
            walls[i][1] = wy;
        }
        RobotWalkingTheMaze robotWalkingTheMaze = new RobotWalkingTheMaze();
        robotWalkingTheMaze.solution(x, y, walls);
    }
}