本文主要是介绍JAVA练习118-逃离大迷宫，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

在一个 10^6 x 10^6 的网格中，每个网格上方格的坐标为 (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^6
• source.length == target.length == 2
• 0 <= sx, sy, tx, ty < 10^6
• source != target
• 题目数据保证 source 和 target 不在封锁列表内

分析：

方法：BFS

这道题很容易想到用 BFS 或 DFS 将整个网格走一遍看能不能到达终点，但是网格是 10^6 x 10^6 的，全遍历完，时间空间都得超，那么有没有方法可以少走一些？提示中给出了 blocked 的数量最大数量为 200，那么我们可以根据这个 blocked 的位置来推算起点和终点是否是连通的。

首先，起点和终点不能连通的条件就是 blocked 点组成的线将起点或终点围住，只要起点和终点的周围能走的点数大于能被围住的面积最大值，那么这些 block 点就不能围住他们，起点和终点就一定有一条路线连通。能围住这两个点的只有两种情况：

没有边界时：

令边长为 a，b，block 最大数量为 max，那么面积 size = a * b = (max - b) * b，要想面积最大，max - b 就要趋近于 b，所以当 a = b = max / 2 时最大，所以最大面积不超过 max ^ 2 / 4。

当有边界时，以两边为边界时最大：

依然令 block 最大数量为 max，因为是点，所以不能用三角形面积计算，已知区域靠边界的最大边长为 max - 1，所以可以用求和公式 Sn = (a1 + an) * n / 2，所以最大面积不超过 (1 + max - 1) * (max - 1) / 2 = (max - 1) * max / 2。

我们取两个的最大值——(max - 1) * max / 2。

我们可以用 BFS 的方法进行遍历，统计起点和终点能走的点数，与最大值进行比较即可。注意：如果遍历时相遇了，直接返回 true 即可。

时间复杂度：O(n) 
空间复杂度：O(n)

class Solution {

    //创建集合存储不能走的点
    HashSet<Long> set = new HashSet<>();
    //网格边长
    long len = 1000000;
    //四个方向
    int[][] dirs = new int[][]{{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    //包围的最大面积
    int max = 200 * 199 / 2;

    public boolean isEscapePossible(int[][] blocked, int[] s, int[] t) {
        //最大面积
        max = blocked.length * (blocked.length-1) / 2;
        //将禁止点转化为一维存储
        for(int[] block: blocked){
            set.add(block[0] * len + block[1]);
        }
        return bfs(s, t) && bfs(t, s);
    }

    public boolean bfs(int[] m, int[] n){
        //创建集合存储走过的点
        HashSet<Long> went = new HashSet<>();
        //加入起点
        went.add(m[0] * len + m[1]);
        //创建队列
        Deque<int[]> queue = new ArrayDeque<>();
        //入队
        queue.addLast(m);
        //遍历
        while(!queue.isEmpty() && went.size() <= max){
            //出队
            int[] point = queue.pollFirst();
            //两点相遇
            if(n[0] == point[0] && n[1] == point[1]){
                return true;
            }
            //往四个方向走
            for(int[] dir: dirs){
                //记录坐标
                int i = point[0] + dir[0], j = point[1] + dir[1];
                //转成一维
                long k = i * len + j;
                //没越界且没走过且能走，入队
                if(i >= 0 && i < len && j >= 0 && j < len && !set.contains(k) && !went.contains(k)){
                    //入队
                    queue.addLast(new int[]{i, j});
                    //添加点到集合
                    went.add(k);
                }
            }
        }
        return went.size() > max;
    }

}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/escape-a-large-maze

这篇关于JAVA练习118-逃离大迷宫的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！