题目

在一个 10⁶ x 10⁶ 的网格中，每个网格上方格的坐标为 (x, y) 。

现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。

每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。

只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

示例 1：

输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
输出：false
解释：
从源方格无法到达目标方格，因为我们无法在网格中移动。
无法向北或者向东移动是因为方格禁止通行。
无法向南或者向西移动是因为不能走出网格。

示例 2：

输入：blocked = [], source = [0,0], target = [999999,999999]
输出：true
解释：
因为没有方格被封锁，所以一定可以到达目标方格。

提示：

• 0 <= blocked.length <= 200
• blocked[i].length == 2
• 0 <= xi, yi < 10⁶
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 10⁶
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

思路

离散化

解法

class Solution {
    public boolean isEscapePossible(int[][] A, int[] src, int[] des) {
        if (A.length == 0 || A[0].length == 0)
            return true;
        TreeSet<Integer> rows = new TreeSet<>(), cols = new TreeSet<>();
        for (int tmp[] : A) {
            if (tmp[0] == src[0] && tmp[1] == src[1] || tmp[0] == des[0] && tmp[1] == des[1])
                return false;
            rows.add(tmp[0]);
            cols.add(tmp[1]);
        }
        rows.add(src[0]);rows.add(des[0]);rows.add(0);rows.add(99999);
        cols.add(src[1]);cols.add(des[1]);cols.add(0);cols.add(99999);
        Map<Integer, Integer> mapX = new HashMap<>(), mapY = new HashMap<>();
        int x = 0, y = 0, preX = -1, preY = -1;
        for (int r : rows) {
            if (preX + 1 != r)
                x++;
            mapX.put(r, x++);
            preX = r;
        }
        for (int c : cols) {
            if (preY + 1 != c)
                y++;
            mapY.put(c, y++);
            preY = c;
        }
        boolean graph[][] = new boolean[x][y];
        for (int tmp[] : A) {
            graph[mapX.get(tmp[0])][mapY.get(tmp[1])] = true;
        }
        return doBFS(graph, new int[] {mapX.get(src[0]),mapY.get(src[1])}, new int[] {mapX.get(des[0]),mapY.get(des[1])}, x, y);
    }

    private boolean doBFS(boolean graph[][], int[] src, int[] des, int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(src);
        final int dir[][] = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        while (!queue.isEmpty()) {
            int cur[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = dir[i][0] + cur[0], ny = dir[i][1] + cur[1];
                if (nx < 0 || nx >= x || ny < 0 || ny >= y || graph[nx][ny])
                    continue;
                graph[nx][ny] = true;
                if (des[0] == nx && des[1] == ny)
                    return true;
                queue.offer(new int[] { nx, ny });
            }
        }
        return false;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现