力扣-1036. 逃离大迷宫

在一个 106 x 106 的网格中，每个网格上方格的坐标为 (x, y) 。
现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格 不 在给出的封锁列表 blocked 上。同时，不允许走出网格。
只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。

class Solution {
    /**
     * 从source找到了target
     */
    private static final int FOUND = 1;
    /**
     * 超出了包围圈
     */
    private static final int OVER = 2;
    /**
     * 被圈住了
     */
    private static final int BLOCKED = 3;
    /**
     * 上下左右四个方向
     */
    private static final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        int n = blocked.length;
        if (n <= 1) {
            return true;
        }
        // 最大可围住的面积
        // 从一个点开始搜索，只要能突破最大可围住的面积，说明它不会被围住
        int max = n * (n - 1) / 2;
        // 将blocked数组转换成哈希表方便快速查找
        Set<Integer> blockedSet = new HashSet<>();
        for (int[] block : blocked) {
            blockedSet.add(convert(block[0], block[1]));
        }
        // 使用bfs来搜索
        int result = bfs(blockedSet, source, target, max);
        // FOUND，表示能从source找到target
        if (result == FOUND) {
            return true;
        } else if (result == BLOCKED) {
            // BLOCKED，表示source被围住了，那么source在围住的面积中还没有找到target
            // 说明 target 没有在围住的面积中
            return false;
        }
        // 看 target 有没有被围住
        return bfs(blockedSet, target, source, max) != BLOCKED;
    }
    private int bfs(Set<Integer> blockedSet, int[] source, int[] target, int max) {
        // 记录是否被访问过
        Set<Integer> visited = new HashSet<>();
        visited.add(convert(source[0], source[1]));
        // bfs使用的队列
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(source);
        // bfs开始
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();

            // 向四个方向扩散
            for (int[] dir : DIRS) {
                // 计算新坐标值
                int x = pos[0] + dir[0];
                int y = pos[1] + dir[1];
                // 转成一维坐标
                int flat = convert(x, y);
                // 如果 x, y 是合法值，并且不是blocked坐标，且没有被访问过，表示可访问
                if (x >= 0 && x < 1000000 && y >= 0 && y < 1000000 && !blockedSet.contains(flat) && !visited.contains(flat)) {
                    // 如果找到了 target 坐标
                    if (x == target[0] && y == target[1]) {
                        return FOUND;
                    }
                    // 标记为已访问
                    visited.add(flat);
                    // 访问的坐标数大于了被围住的面积
                    // 说明从 source 出发可以突破被围住
                    if (visited.size() > max) {
                        return OVER;
                    }
                    // 将新坐标加入队列，继续搜索
                    queue.offer(new int[] {x, y});
                }
            }
        }
        return BLOCKED;
    }
    private int convert(int x, int y) {
        // 二维坐标转一维
        return x * 1000001 + y;
    }

方法：BFS

今天这道题最简单的方法就是使用 BFS 来求解。
但是，请看提示中的数据范围，整个坐标系统的范围有 10610^6106 那么大，直接使用 BFS 求解肯定超时。
所以，我们需要另辟蹊径。
再看提示中给出的 blocked 数组的范围最大只有 200，也就是说最多只有 200 个方格是不可访问的。
那么，我们可以思考一下 200 个 方格最大可围成多大的面积呢？
显然，合理利用两条直角边界，可以使得面积最大，最大为 n * (n - 1) / 2。

如果 source 落在左上角，target 落在右边区域，那么，它们俩无论如何都连不在一起。
当然，上图所示的是最大面积的情况，其实，还有以下这些情况，统统都是不可行的。

可以看到，在有限的障碍物数量的条件下，能围出的最大面积就是最上面那个图的样子。
所以，我们并不需要从 source 一定要搜索到 target，我们只要保证 source 和 target 都没有被单独围住就可以了。
因此，我们可以尝试分别从 source 和 target 出发，使用 BFS 搜索，如果它们搜索的范围大于了可以被围住的最大面积，那就说明它们俩肯定可以连在一起。

代码中运用到的一些技巧：
我们并不需要同时进行双向 BFS，可以先从 source 出发，如果能找到 target，可直接返回 true，如果 source 被围住了（且没找到 target），可直接返回 false。

二维坐标转一维坐标，return x * 1000001 + y;，因为坐标系范围为 10610^6106，所以，我们假设二维坐标系是一个行列为 1000001 大小的二维数组，这里不用考虑溢出的问题，我们只要保证计算后的值唯一即可。
向四个方向遍历，我们使用 DIRS 二维数组表示。