英文原文
There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).
We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).
Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.
Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.
Example 1:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false Explanation: The target square is inaccessible starting from the source square because we cannot move. We cannot move north or east because those squares are blocked. We cannot move south or west because we cannot go outside of the grid.
Example 2:
Input: blocked = [], source = [0,0], target = [999999,999999] Output: true Explanation: Because there are no blocked cells, it is possible to reach the target square.
Constraints:
0 <= blocked.length <= 200blocked[i].length == 20 <= xi, yi < 106source.length == target.length == 20 <= sx, sy, tx, ty < 106source != target- It is guaranteed that
sourceandtargetare not blocked.
中文题目
在一个 106 x 106 的网格中，每个网格上方格的坐标为 (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 < 106source.length == target.length == 20 <= sx, sy, tx, ty < 106source != target- 题目数据保证
source和target不在封锁列表内
通过代码
高赞题解
class Solution {
static int dirs[][] = new int[][]{{0,1}, {1,0}, {-1,0}, {0,-1}};
static int limit = (int)1e6;
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
Set<String> blocks = new HashSet<>();
for(int block[] : blocked)
blocks.add(block[0] + ":" + block[1]);
return bfs(source, target, blocks) && bfs(target, source, blocks);
}
public boolean bfs(int[] source, int[] target, Set<String> blocks){
Set<String> seen = new HashSet<>();
seen.add(source[0] + ":" + source[1]);
Queue<int[]> bfs = new LinkedList<>();
bfs.offer(source);
while(!bfs.isEmpty()){
int cur[] = bfs.poll();
for(int dir[] : dirs){
int nextX = cur[0] + dir[0];
int nextY = cur[1] + dir[1];
if(nextX < 0 || nextY < 0 || nextX >= limit || nextY >= limit) continue;
String key = nextX + ":" + nextY;
if(seen.contains(key) || blocks.contains(key)) continue;
if(nextX == target[0] && nextY == target[1]) return true;
bfs.offer(new int[]{nextX, nextY});
seen.add(key);
}
// 因为 blocked 的 length 是 200
// 如果使用这 200 个 block 可以围成最大的区域是 19900，如下：
/*
0th _________________________
|O O O O O O O X
|O O O O O O X
|O O O O O X
|O O O O X
.O O O X
.O O X
.O X
200th |X
从上面可以计算出 block（即 X）可以围城的最大区域(是一个角的三角形)，大小计算如下：
1 + 2 + 3 + 4 + ... + 199 = (1 + 199) * 199 / 2 = 19900
这里我们向上取整为 20000。
*/
// 也就是说，如果迭代了 20000 步还能继续走的话，那么是肯定可以到达 target 的
if(seen.size() == 20000) return true;
}
return false;
}
}在刷题的时候：
如果你觉得自己数据结构与算法基础不够扎实，那么请点这里，这里包含了一个程序员 5 年内需要的所有算法知识
如果你感觉刷题太慢，或者感觉很困难，或者赶时间，那么请点这里。这里用 365 道高频算法题，带你融会贯通算法知识，做到以不变应万变
回溯、贪心和动态规划，是算法面试中的三大难点内容，如果你只是想搞懂这三大难点内容 请点这里
以上三个链接中的内容，都支持 Java/C++/Python/js/go 五种语言
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 3417 | 11383 | 30.0% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
