题目大意：
逃离大迷宫
在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。
我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。
只有在可以通过一系列的移动到达目标方格时才返回 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 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1036
解题思路分析：
因为本题给出的矩阵大小在100万级别，所以本题被定义为Hard级别。如果单纯的使用bfs做广度优先遍历，那么搜索次数（时间复杂度）将会达到100万乘以100万级别，这可定会超时。因此我们需要考虑如何剪枝。
看了一下提示的条件，幸好blocked数组的大小并没有那么夸张，最多只有200，因此我们应该考虑从这里下手思考剪枝思路。
试想，如果想从source出发能够到达target，那么需要他们各自的周围不能被blocked完全封锁（类似围棋）。如果 source 和 target 两点均不能被 blocked 封锁，那么必定存在至少一条路径能使其相连。再反过来想，要想包围住一个点，我们最多需要4个block（上下左右四个点），特殊情况下，比如该点在矩阵的角落或者矩阵边上时，也需要2个和3个block将其包围。同理，如果想包围住2个连续的点，我们需要至少3个，至多6个block。总结来看，要想封锁住n个点，我们至少需要n+1个block才能将其包围。因此，当bfs进行中，记录bfs用的Queue的size大于 blocked 数组size时，说明 blocked数组是无法封锁当前点的。
解题思路大致如下：
- 先以source为起点开始bfs。如果 blocked 能够封锁source，返回false。如果不能则：
- 以target 为起点开始bfs。 如果 blocked 能够封锁target，返回false。否则返回true。
- 在bfs中如果能直接找到另外一个点，则直接返回true。
看下完整代码：
int[][] directions={{1,0},{0,1},{-1,0},{0,-1}}; // 定义bfs四个方向
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
int blockSize = blocked.length; // blocked数量
Set<String> blockedSet = new HashSet<>(); // 将blocked转化为set
for(int[] b : blocked){
blockedSet.add(b[0]+"_"+b[1]);
}
Set<String> visited = new HashSet<>(); // 记录已访问节点
visited.add(source[0]+"_"+source[1]); // 将source加入已访问节点
// 以source为起点开始bfs
boolean res1 = bfs(visited,blockedSet, source, target[0]+"_"+target[1], blockSize);
if(!res1){ // 如果source被封锁，直接返回false
return false;
}
visited.clear(); // 清空已访问列表
visited.add(target[0]+"_"+target[1]); // 将target加入已访问列表
// 以target为起点开始bfs
boolean res2 = bfs(visited,blockedSet, target, source[0]+"_"+source[1], blockSize);
return res2;
}
private boolean bfs(Set<String> visited,Set<String> blockedSet,
int[] source, String target,int blockSize){
Queue<int[]> q = new LinkedList<>(); // 建立bfs用的Queue
q.offer(source); // 将起始节点加入Queue
while(q.size()>0){ // 如果Queue的size大于0，保持循环。
int[] point =q.poll(); // 从Queue中取出一个节点元素
for(int[]direction : directions){ // 将此节点向四周扩散
// 得到扩散后的节点
int row = point[0]+direction[0], col=point[1]+direction[1];
String key=row+"_"+col; // 利用坐标生成一个key
// 如果该节点没有越界，并且不是block，并且没被访问过
if(row>=0 && col>=0 && row <1000000 && col<1000000
&& !blockedSet.contains(key) && !visited.contains(key)){
// 如果该节点即是target，说明找到联通路径，返回true。
if(key.equals(target)){
return true;
}
// 将该节点的key加入已访问列表
visited.add(key);
// 将该节点加入bfs的Queue
q.offer(new int[]{row, col});
// 如果当前Queue中的数量大于blockSize，说明block无法封锁source节点
if(q.size() >= blockSize){
// 返回true。
return true;
}
}
}
}
return false;
}本题解法运行时间为71ms。
Runtime: 71 ms, faster than 74.61% of Java online submissions for Escape a Large Maze.
Memory Usage: 41.4 MB, less than 80.00% of Java online submissions for Escape a Large Maze.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1036-escape-a-large-maze-解题思路分析/