1036. Escape a Large Maze
Description
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.
Solutions
Solution 1: DFS
The problem can be interpreted as determining whether it is possible to move from a source point to a target point in a $10^6 \times 10^6$ grid, given a small number of blocked points.
Since the number of blocked points is small, the maximum area that can be blocked is no more than $|blocked|^2 / 2$. Therefore, we can perform a depth-first search (DFS) starting from both the source and the target points. The search continues until either the target point is reached or the number of visited points exceeds $|blocked|^2 / 2$. If either condition is satisfied, return $\textit{true}$. Otherwise, return $\textit{false}$.
Time complexity is $O(m)$, and space complexity is $O(m)$, where $m$ is the size of the blocked region. In this problem, $m \leq |blocked|^2 / 2 = 200^2 / 2 = 20000$.
Python3
class Solution:
def isEscapePossible(
self, blocked: List[List[int]], source: List[int], target: List[int]
) -> bool:
def dfs(source: List[int], target: List[int], vis: set) -> bool:
vis.add(tuple(source))
if len(vis) > m:
return True
for a, b in pairwise(dirs):
x, y = source[0] + a, source[1] + b
if 0 <= x < n and 0 <= y < n and (x, y) not in s and (x, y) not in vis:
if [x, y] == target or dfs([x, y], target, vis):
return True
return False
s = {(x, y) for x, y in blocked}
dirs = (-1, 0, 1, 0, -1)
n = 10**6
m = len(blocked) ** 2 // 2
return dfs(source, target, set()) and dfs(target, source, set())
Java
class Solution {
private final int n = (int) 1e6;
private int m;
private Set<Long> s = new HashSet<>();
private final int[] dirs = {-1, 0, 1, 0, -1};
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
for (var b : blocked) {
s.add(f(b[0], b[1]));
}
m = blocked.length * blocked.length / 2;
int sx = source[0], sy = source[1];
int tx = target[0], ty = target[1];
return dfs(sx, sy, tx, ty, new HashSet<>()) && dfs(tx, ty, sx, sy, new HashSet<>());
}
private boolean dfs(int sx, int sy, int tx, int ty, Set<Long> vis) {
if (vis.size() > m) {
return true;
}
for (int k = 0; k < 4; ++k) {
int x = sx + dirs[k], y = sy + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (x == tx && y == ty) {
return true;
}
long key = f(x, y);
if (!s.contains(key) && vis.add(key) && dfs(x, y, tx, ty, vis)) {
return true;
}
}
}
return false;
}
private long f(int i, int j) {
return (long) i * n + j;
}
}
C++
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
const int n = 1e6;
int m = blocked.size() * blocked.size() / 2;
using ll = long long;
unordered_set<ll> s;
const int dirs[5] = {-1, 0, 1, 0, -1};
auto f = [&](int i, int j) {
return (ll) i * n + j;
};
for (const auto& b : blocked) {
s.insert(f(b[0], b[1]));
}
int sx = source[0], sy = source[1];
int tx = target[0], ty = target[1];
unordered_set<ll> vis1, vis2;
auto dfs = [&](this auto&& dfs, int sx, int sy, int tx, int ty, unordered_set<ll>& vis) -> bool {
vis.insert(f(sx, sy));
if (vis.size() > m) {
return true;
}
for (int k = 0; k < 4; ++k) {
int x = sx + dirs[k], y = sy + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (x == tx && y == ty) {
return true;
}
auto key = f(x, y);
if (!s.contains(key) && !vis.contains(key) && dfs(x, y, tx, ty, vis)) {
return true;
}
}
}
return false;
};
return dfs(sx, sy, tx, ty, vis1) && dfs(tx, ty, sx, sy, vis2);
}
};
Go
func isEscapePossible(blocked [][]int, source []int, target []int) bool {
const n = 1_000_000
m := len(blocked) * len(blocked) / 2
dirs := [5]int{-1, 0, 1, 0, -1}
f := func(i, j int) int64 {
return int64(i*n + j)
}
s := make(map[int64]bool)
for _, b := range blocked {
s[f(b[0], b[1])] = true
}
var dfs func(sx, sy, tx, ty int, vis map[int64]bool) bool
dfs = func(sx, sy, tx, ty int, vis map[int64]bool) bool {
key := f(sx, sy)
vis[key] = true
if len(vis) > m {
return true
}
for k := 0; k < 4; k++ {
x, y := sx+dirs[k], sy+dirs[k+1]
if x >= 0 && x < n && y >= 0 && y < n {
if x == tx && y == ty {
return true
}
key := f(x, y)
if !s[key] && !vis[key] && dfs(x, y, tx, ty, vis) {
return true
}
}
}
return false
}
sx, sy := source[0], source[1]
tx, ty := target[0], target[1]
return dfs(sx, sy, tx, ty, map[int64]bool{}) && dfs(tx, ty, sx, sy, map[int64]bool{})
}
TypeScript
function isEscapePossible(blocked: number[][], source: number[], target: number[]): boolean {
const n = 10 ** 6;
const m = (blocked.length ** 2) >> 1;
const dirs = [-1, 0, 1, 0, -1];
const s = new Set<number>();
const f = (i: number, j: number): number => i * n + j;
for (const [x, y] of blocked) {
s.add(f(x, y));
}
const dfs = (sx: number, sy: number, tx: number, ty: number, vis: Set<number>): boolean => {
vis.add(f(sx, sy));
if (vis.size > m) {
return true;
}
for (let k = 0; k < 4; k++) {
const x = sx + dirs[k],
y = sy + dirs[k + 1];
if (x >= 0 && x < n && y >= 0 && y < n) {
if (x === tx && y === ty) {
return true;
}
const key = f(x, y);
if (!s.has(key) && !vis.has(key) && dfs(x, y, tx, ty, vis)) {
return true;
}
}
}
return false;
};
return (
dfs(source[0], source[1], target[0], target[1], new Set()) &&
dfs(target[0], target[1], source[0], source[1], new Set())
);
}
Rust
use std::collections::HashSet;
impl Solution {
pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
const N: i64 = 1_000_000;
let m = (blocked.len() * blocked.len()) as i64 / 2;
let f = |i: i64, j: i64| -> i64 { i * N + j };
let mut s: HashSet<i64> = HashSet::new();
for b in &blocked {
s.insert(f(b[0] as i64, b[1] as i64));
}
fn dfs(
sx: i64,
sy: i64,
tx: i64,
ty: i64,
s: &HashSet<i64>,
m: i64,
vis: &mut HashSet<i64>,
) -> bool {
static DIRS: [i64; 5] = [-1, 0, 1, 0, -1];
let key = sx * 1_000_000 + sy;
vis.insert(key);
if vis.len() as i64 > m {
return true;
}
for k in 0..4 {
let x = sx + DIRS[k];
let y = sy + DIRS[k + 1];
let key = x * 1_000_000 + y;
if x >= 0 && x < 1_000_000 && y >= 0 && y < 1_000_000 {
if x == tx && y == ty {
return true;
}
if !s.contains(&key) && vis.insert(key) && dfs(x, y, tx, ty, s, m, vis) {
return true;
}
}
}
false
}
dfs(
source[0] as i64,
source[1] as i64,
target[0] as i64,
target[1] as i64,
&s,
m,
&mut HashSet::new(),
) && dfs(
target[0] as i64,
target[1] as i64,
source[0] as i64,
source[1] as i64,
&s,
m,
&mut HashSet::new(),
)
}
}