class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
}
};
1036. 逃离大迷宫
在一个 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 != targetsource 和 target 不在封锁列表内原站题解
java 解法, 执行用时: 43 ms, 内存消耗: 44.9 MB, 提交时间: 2023-06-25 09:49:00
class Solution {
private static final int BOUND = (int)1e6;
private static final long HASH_BOUND = (long)1e6;
private static final int[][] dir = new int[][]{{1,0},{0,1},{0,-1},{-1,0}};
private Set<Long> block;
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
int max = blocked.length * (blocked.length - 1) / 2;
block = new HashSet<>();
for(int[] p: blocked)
block.add(p[0] * HASH_BOUND + p[1]);
return bfs(source, target, max) && bfs(target, source, max);
}
private boolean bfs(int[] start, int[] end, int max){
List<int[]> list = new ArrayList<>(){{add(start);}};
Set<Long> explored = new HashSet<>(){{add(start[0] * HASH_BOUND + start[1]);}};
for(int i=0;i<list.size() && list.size() <= max;i++)
for(int j=0;j<dir.length;j++){
int[] point = new int[]{list.get(i)[0] + dir[j][0], list.get(i)[1] + dir[j][1]};
long p = point[0] * HASH_BOUND + point[1];
if(point[0] >= 0 && point[0] < BOUND && point[1] >= 0 && point[1] < BOUND && !explored.contains(p) && !block.contains(p)){
if(point[0] == end[0] && point[1] == end[1])
return true;
explored.add(p);
list.add(point);
}
}
return list.size() > max;
}
}
golang 解法, 执行用时: 60 ms, 内存消耗: 8.2 MB, 提交时间: 2023-06-25 09:48:33
func isEscapePossible(blocked [][]int, source []int, target []int) bool {
bound, block, max, dir := 1000000, map[int]bool{}, len(blocked) * (len(blocked) - 1) / 2, [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
for _, b := range blocked{
block[hash(b)] = true
}
bfs := func(start, end []int)bool {
list := [][]int{start}
explored := map[int]bool{}
explored[hash(start)] = true
for i := 0; i < len(list) && len(list) <= max; i++{
for _, d := range dir {
point := make([]int, 2)
point[0] = list[i][0] + d[0]
point[1] = list[i][1] + d[1]
h := hash(point)
if point[0] >= 0 && point[0] < bound && point[1] >= 0 && point[1] < bound && !explored[h] && !block[h]{
if point[0] == end[0] && point[1] == end[1]{
return true
}
explored[h] = true
list = append(list, point)
}
}
}
return len(list) > max
}
return bfs(source, target) && bfs(target, source)
}
func hash(point []int) int {
return point[0] * 1000000 + point[1]
}
javascript 解法, 执行用时: 144 ms, 内存消耗: 56.7 MB, 提交时间: 2023-06-25 09:48:16
/**
* @param {number[][]} blocked
* @param {number[]} source
* @param {number[]} target
* @return {boolean}
*/
const BOUND = 1000000
const DIR = [[0, 1], [1, 0], [-1,0],[0,-1]]
var isEscapePossible = function(blocked, source, target) {
const max = Math.floor(blocked.length * (blocked.length - 1) / 2);
block = new Set()
for(const b of blocked)
block.add(b[0] * BOUND + b[1])
bfs = function(start, end){
const list = [start], explored = new Set()
explored.add(start[0] * BOUND + start[1])
for(let i=0;i<list.length && list.length <= max; i++)
for(const dir of DIR){
const point = [list[i][0] + dir[0], list[i][1] + dir[1]]
const hash = point[0] * BOUND + point[1]
if(point[0] >= 0 && point[0] < BOUND && point[1] >= 0 && point[1] < BOUND && !block.has(hash) && !explored.has(hash)){
if(point[0] == end[0] && point[1] == end[1])
return true
explored.add(hash)
list.push(point)
}
}
return list.length > max
}
return bfs(source, target) && bfs(target, source)
};
python3 解法, 执行用时: 360 ms, 内存消耗: 22.8 MB, 提交时间: 2023-06-25 09:47:57
'''
blocked区域的两种形式，棋盘角落和中间。
'''
BOUND = int(1e6)
class Solution:
def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
blocked, MAX = {tuple(p) for p in blocked}, len(blocked) * (len(blocked) - 1) // 2
def bfs(start, end):
points,idx,explored = [start], 0, {tuple(start)}
while idx < len(points):
for dx, dy in (0, 1), (1,0),(-1,0),(0, -1):
nx, ny = points[idx][0] + dx, points[idx][1] + dy
if 0 <= nx < BOUND and 0 <= ny < BOUND and (nx, ny) not in blocked and (nx, ny) not in explored:
if [nx, ny] == end:
return True
explored.add((nx, ny))
points.append((nx, ny))
if len(points) > MAX:
return True
idx += 1
return False
return bfs(source, target) and bfs(target, source)