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 <= 200blocked[i].length == 20 <= xi, yi < 10^6source.length == target.length == 20 <= sx, sy, tx, ty < 10^6source != 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 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 went = new HashSet<>(); //加入起点 went.add(m[0] * len + m[1]); //创建队列 Deque 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