LeetCode1036.逃离大迷宫：「BFS & 哈希表 & 包围圈面积」

浏览次数 : 次 2022-01-11

博文字数统计 : 2.5k字 | 阅读所需时长 : 10分

× 文章目录

1. LeetCode1036.逃离大迷宫：「BFS & 哈希表 & 包围圈面积」

LeetCode1036：逃离大迷宫
- 时间：2022-01-11
- 力扣难度：Hard
- 个人难度：Hard
- 数据结构：数组、哈希表
- 算法：BFS、DFS

LeetCode1036.逃离大迷宫：「BFS & 哈希表 & 包围圈面积」

1. 题目描述

题目：原题链接
- 在一个 $10^6×10^6$ 的网格中，每个网格上方格的坐标为 (x, y) 。
- 现在从源方格 source = [sx, sy] 开始出发，意图赶往目标方格 target = [tx, ty] 。
- 数组 blocked 是封锁的方格列表，其中每个 blocked[i] = [xi, yi] 表示坐标为 (xi, yi) 的方格是禁止通行的。
- 每次移动，都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。同时，不允许走出网格边界。
- 只有在可以通过一系列的移动从源方格 source 到达目标方格 target 时才返回 true。否则，返回 false。
输入输出规范
- 输入：封锁格的数组、起点和终点
- 输出：是否可以到达终点，布尔型
输入输出示例
- 输入：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
- 输出：false

2. 方法一：BFS + 哈希表 + 包围圈面积

思路：根据包围圈最大面积进行BFS
- 本题是一个迷宫、棋盘类型的矩阵问题，基本可以确定解题的基本思路为搜索、回溯
- 但是由于本题的矩阵大小为 $10^6×10^6$，即共一亿个网格，直接暴力BFS肯定是会TLE超时的，因此需要思考如何优化搜索过程，进行剪枝
- 首先，我们先分析一下何种情况下，无法从起点到达终点
  - 起点或终点本身就是一个障碍物
  - 起点或终点被障碍物包围了，且一个在包围圈内，另一个在包围圈外
- 根据无法到达终点的情况的特点，可以得到这种情况下，包围圈的面积与被包围的起始位置可到达的位置个数之间的关系
  - 此时对于包围圈中的起点或者终点，其只有有限个可以到达的位置
  - 将每一个网格的面积视为1，可以到达的位置个数就是包围圈的面积
- 因此，当我们对起点和终点进行BFS广搜时，如果其可以到达的位置个数超过了包围圈的面积，就可以表明起点与终点连通
- 那么，本题就通过对BFS过程中是否经过起点、终点的判断，以及对可达网格个数的计数并与包围圈面积进行比较的方式，将BFS的时间复杂度从$O(Grid_{area})$优化、剪枝到$O(Block_{area})$
- 实际上问题的关键就转变为给定的block障碍物数组所围成的包围圈的面积的求解
包围圈的最大面积
- 对于给定的block障碍物数组，可以判断其是否是一个闭合的曲线，如果闭合，求其面积，不闭合时表示面积为0，起点和终点一定连通
- 但是，判断是否为一个闭合的曲线的过程较为复杂，不容易实现
- 因此我们可以适当提高一些时间复杂度，只需要根据block数组的长度来求出其可能围成的包围圈的最大面积，而不考虑block数组的具体位置到底有没有形成包围圈
- 此时，对于给定数量个障碍物，考虑以下几种情况构成包围圈的情况
  - 情况一：包围圈每个障碍物在横向或竖向相邻，围成一个矩形，当矩形恰好为正方形的时候面积最大
  - 情况二：包围圈每个障碍物在横向或竖向不相邻，而是斜对角相邻，此时面积要比情况一大
  - 情况三：由于迷宫有边界，所以障碍物借用边界作为包围圈的一部分，并且按照情况二的斜对角相邻方式放置时，面积是所有情况中最大的
  - 其他情况：如障碍物有浪费等，此时面积肯定不是最大
起点终点的连通性分析
- 确定了包围圈的最大面积后，就可以分别对起点、终点进行BFS，对其可达的网格个数进行计数，进而判断起点和终点是否连通
- 具体而言，起点和终点连通也分为多种情况
  - 起点或终点可达的网格个数大于给定的block数组围成的包围圈的面积
  - 起点或终点可达的网格个数小于包围圈面积，但是两者都在包围圈中，即BFS过程中经过了终点或者起点
具体解题步骤
- 首先，需要计算指定block数组的长度下，包围圈的最大面积，对于 n 个障碍物而言，最大包围圈如上图所示，面积为$1+2+…+n-1 = n*(n-1)/2$
- 其次，通过两个哈希表(blockSet、visited)分别来存储障碍物的位置，以及BFS过程中经过的网格点的位置
- 然后，分别对起点和终点进行BFS搜索，通过循环来模拟向四个方向的广度搜索，每次都将到达的网格坐标记录下来
  - 如果超出边界，或者是障碍物，即blockSet中存在该网格坐标，直接进行下次循环
  - 如果是终点或者起点，则直接返回true，表示连通
  - 如果是其他情况，将该点添加到visited哈希表中，该表的size就是可达网格的个数
- 最后只需要比较 visited 哈希表的 size 与包围圈最大面积，来判断是否连通
思考一：哈希表存储的元素的格式
- 方式一：由于要存储坐标，可以直接存储坐标拼接而成的字符串，该方式简便但是容易造成空间不足
- 方式二：使用数组(List)来存坐标，同样较为浪费空间
- 方式三：借用哈希的思想，通过 $x*Count + y$ 的方式将坐标转换为一个数字，直接存一个int或long的数字，节省空间，但是要注意避免哈希冲突
- 本题中，因为迷宫大小是 $10^6×10^6$，所以有保险起见使用第三种方式，为了避免哈希冲突，哈希散列的常数使用迷宫的长度 $10^6$确保不发生冲突，实际上，根据测试用例的不同，该数字可以在一定程度上减小
思考二：BFS过程中，当前一轮的网格的存储
- 类似二叉树层序遍历，BFS中存储本轮结果的数据结构一般使用队列
- 本题使用双向队列LinkedList，初始时添加起点或终点，对于可达的网格，在循环中添加到队列中
复杂度分析：n 是 block 数组的长度，即障碍物的个数
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$

题解：使用List作为哈希存储的元素，使用字符串的话类似(StringBuilder)

final int GRID_EDGE = (int) 1e6;
int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    if (source == null || source.length == 0) return false;
    if (target == null || target.length == 0) return false;
    if (blocked == null || blocked.length == 0) return true;
    int n = blocked.length;
    final int AREA = n * (n - 1) / 2;
    Set<List<Integer>> blockSet = new HashSet<>();
    for (int[] grid : blocked) {
        List<Integer> list = new ArrayList<>(2);
        list.add(grid[0]);
        list.add(grid[1]);
        blockSet.add(list);
    }
    return bfs(source, target, blockSet, AREA) && bfs(target, source, blockSet, AREA);
}

private boolean bfs(int[] source, int[] target, Set<List<Integer>> blockSet, int AREA) {
    Set<List<Integer>> visited = new HashSet<>();
    Deque<int[]> deque = new LinkedList<>();
    List<Integer> list = new ArrayList<>(2);
    list.add(source[0]);
    list.add(source[1]);
    deque.addLast(source);
    visited.add(list);
    while (!deque.isEmpty()) {
        // 可达网格个数大于包围圈面积，连通
        if (visited.size() > AREA) return true;
        int[] cur = deque.poll();
        int x = cur[0];
        int y = cur[1];
        //  经过了起点、终点，连通
        if (x == target[0] && y == target[1]) return true;
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 0 || nx >= GRID_EDGE || ny < 0 || ny >= GRID_EDGE) continue;
            int[] next = new int[]{nx, ny};
            list = new ArrayList<>(2);
            list.add(nx);
            list.add(ny);
            if (blockSet.contains(list) || visited.contains(list)) continue;
            deque.addLast(next);
            visited.add(list);
        }
    }
    return visited.size() > AREA;
}

题解：使用方式三哈希表的元素为散列后的数字

final int GRID_EDGE = (int) 1e6;
int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
    if (source == null || source.length == 0) return false;
    if (target == null || target.length == 0) return false;
    if (blocked == null || blocked.length == 0) return true;
    int n = blocked.length;
    final int AREA = n * (n - 1) / 2;
    Set<Long> blockSet = new HashSet<>();
    for (int[] grid : blocked) {
        long hash = (long) grid[0] * GRID_EDGE + grid[1];
        blockSet.add(hash);
    }
    return bfs(source, target, blockSet, AREA) && bfs(target, source, blockSet, AREA);
}

private boolean bfs(int[] source, int[] target, Set<Long> blockSet, int AREA) {
    Set<Long> visited = new HashSet<>();
    Deque<int[]> deque = new LinkedList<>();
    long hash = (long) source[0] * GRID_EDGE + source[1];
    deque.addLast(source);
    visited.add(hash);
    while (!deque.isEmpty()) {
        // 可达网格个数大于包围圈面积，连通
        if (visited.size() > AREA) return true;
        int[] cur = deque.poll();
        int x = cur[0];
        int y = cur[1];
        //  经过了起点、终点，连通
        if (x == target[0] && y == target[1]) return true;
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 0 || nx >= GRID_EDGE || ny < 0 || ny >= GRID_EDGE) continue;
            hash = (long) nx * GRID_EDGE + ny;
            if (blockSet.contains(hash) || visited.contains(hash)) continue;
            deque.addLast(new int[]{nx, ny});
            visited.add(hash);
        }
    }
    return visited.size() > AREA;
}

参考资料

宫水三叶的题解：https://leetcode-cn.com/problems/escape-a-large-maze/solution/gong-shui-san-xie-bfs-gei-ding-zhang-ai-8w63o/

本文作者： Chthollists
发布时间： 2022-01-11 18:23:12
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode1036.逃离大迷宫：「BFS & 哈希表 & 包围圈面积」
本文链接： https://chthollists.github.io/post/2cae18a6.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！