Formatted question description: https://leetcode.ca/all/1036.html

1036. Escape a Large Maze

Hard

Description

In a 1 million by 1 million grid, the coordinates of each grid square are (x, y) with 0 <= x, y < 10^6.

We start at the source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn’t in the given list of blocked squares.

Return true if and only if it is possible to reach the target square through a sequence of 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 can’t walk outside the grid.

Example 2:

Input: blocked = [], source = [0,0], target = [999999,999999]

Output: true

Explanation:

Because there are no blocked cells, it’s possible to reach the target square.

Note:

1. 0 <= blocked.length <= 200
2. blocked[i].length == 2
3. 0 <= blocked[i][j] < 10^6
4. source.length == target.length == 2
5. 0 <= source[i][j], target[i][j] < 10^6
6. source != target

Solution

Since the grid is very large, directly using breadth first search is quite time-consuming. One way is to check whether the source is in a closed area and whether the target is in a closed area. Suppose there are m cells that are blocked. The maximum possible closed area is m * (m - 1) / 2.

Do breadth first search for two times. The first time search from source to target. If target can be reached, then return true without the second search. If at one step, the number of visited cells is greater than m * (m - 1) / 2, then the second search is required. Otherwise, return false without the second search.

The second time search from target to source. If at one step, the number of visited cells is greater than m * (m - 1) / 2, then return true. Otherwise, return false.

• class Solution {
public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
if (blocked == null || blocked.length == 0)
return true;
final int MAX = 1000000;
Set<String> blockedSet = new HashSet<String>();
int blockedSize = blocked.length;
for (int i = 0; i < blockedSize; i++)
int search1 = breadthFirstSearch(MAX, blockedSet, source, target);
if (search1 == 2)
return true;
else if (search1 == 0)
return false;
else {
int search2 = breadthFirstSearch(MAX, blockedSet, target, source);
return search2 > 0;
}
}

public int breadthFirstSearch(final int MAX, Set<String> blockedSet, int[] source, int[] target) {
int blockedSize = blockedSet.size();
int blockedArea = blockedSize * (blockedSize - 1) / 2;
Set<String> visitedSet = new HashSet<String>();
int visitedCount = 1;
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue.offer(source);
while (!queue.isEmpty()) {
int[] cell = queue.poll();
if (cell[0] == target[0] && cell[1] == target[1])
return 2;
for (int[] direction : directions) {
int[] nextCell = {cell[0] + direction[0], cell[1] + direction[1]};
String nextCellStr = Arrays.toString(nextCell);
if (nextCell[0] >= 0 && nextCell[0] < MAX && nextCell[1] >= 0 && nextCell[1] < MAX && !blockedSet.contains(nextCellStr)) {
queue.offer(nextCell);
visitedCount++;
if (visitedCount > blockedArea)
return 1;
}
}
}
}
return 0;
}
}

• // OJ: https://leetcode.com/problems/escape-a-large-maze/
// Time: O(?)
// Space: O(?)
class Solution {
public:
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
unordered_map<int, unordered_set<int>> blk;
for (auto &b : blocked) blk[b[0]].insert(b[1]);
int dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
auto check = [&](vector<int> &from, vector<int> &to) -> int { // 0 -> blocked, 1 -> source & target met, 2 -> from is not enclosed by blocked points
unordered_map<int, unordered_set<int>> seen;
function<int(int, int, int)> dfs = [&](int x, int y, int dist) {
if (x == to[0] && y == to[1]) return 1;
if (dist >= 200) return 2;
for (auto &[dx, dy] : dirs) {
int a = x + dx, b = y + dy;
if (a < 0 || b < 0 || a >= 1e6 || b >= 1e6 || (blk.count(a) && blk[a].count(b)) || seen[a].count(b)) continue;
seen[a].insert(b);
int ans = dfs(a, b, abs(a - from[0]) + abs(b - from[1]));
if (ans) return ans;
}
return 0;
};
return dfs(from[0], from[1], 0);
};
int a = check(source, target);
return a == 1 || (a == 2 && check(target, source));
}
};

• class Solution:
def isEscapePossible(
self, blocked: List[List[int]], source: List[int], target: List[int]
) -> bool:
def dfs(source, target, seen):
x, y = source
if (
not (0 <= x < 10**6 and 0 <= y < 10**6)
or (x, y) in blocked
or (x, y) in seen
):
return False
if len(seen) > 20000 or source == target:
return True
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
next = [x + a, y + b]
if dfs(next, target, seen):
return True
return False

blocked = set((x, y) for x, y in blocked)
return dfs(source, target, set()) and dfs(target, source, set())

############

# 1036. Escape a Large Maze
# https://leetcode.com/problems/escape-a-large-maze/

class Solution:
def isEscapePossible(self, blocked, source, target):
blocked = set(map(tuple, blocked))

def dfs(x, y, target, seen):
if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return False

if len(seen) > 20000 or [x, y] == target: return True
return dfs(x + 1, y, target, seen) or \
dfs(x - 1, y, target, seen) or \
dfs(x, y + 1, target, seen) or \
dfs(x, y - 1, target, seen)

return dfs(source[0], source[1], target, set()) and dfs(target[0], target[1], source, set())


• func isEscapePossible(blocked [][]int, source []int, target []int) bool {
const N = 1e6
dirs := [4][2]int{ {0, -1}, {0, 1}, {1, 0}, {-1, 0} }
block := make(map[int]bool)
for _, b := range blocked {
block[b[0]*N+b[1]] = true
}
var dfs func(source, target []int, seen map[int]bool) bool
dfs = func(source, target []int, seen map[int]bool) bool {
sx, sy := source[0], source[1]
tx, ty := target[0], target[1]
if sx < 0 || sx >= N || sy < 0 || sy >= N || tx < 0 || tx >= N || ty < 0 || ty >= N || block[sx*N+sy] || seen[sx*N+sy] {
return false
}
seen[sx*N+sy] = true
if len(seen) > 20000 || (sx == target[0] && sy == target[1]) {
return true
}
for _, dir := range dirs {
next := []int{sx + dir[0], sy + dir[1]}
if dfs(next, target, seen) {
return true
}
}
return false
}
s1, s2 := make(map[int]bool), make(map[int]bool)
return dfs(source, target, s1) && dfs(target, source, s2)
}

• use std::collections::{HashSet, VecDeque};

const BOUNDARY: i32 = 1_000_000;
const MAX: usize = 20000;

impl Solution {
pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
let mut block = HashSet::with_capacity(blocked.len());
for b in blocked.iter() {
block.insert((b[0], b[1]));
}
bfs(&block, &source, &target) && bfs(&block, &target, &source)
}
}

fn bfs(block: &HashSet<(i32, i32)>, source: &Vec<i32>, target: &Vec<i32>) -> bool {
let dir = vec![(-1, 0), (1, 0), (0, -1), (0, 1)];

let mut queue = VecDeque::new();
let mut vis = HashSet::new();
queue.push_back((source[0], source[1]));
vis.insert((source[0], source[1]));

while !queue.is_empty() && vis.len() < MAX {
let (x, y) = queue.pop_front().unwrap();
if x == target[0] && y == target[1] {
return true;
}
for (dx, dy) in dir.iter() {
let (nx, ny) = (x + dx, y + dy);
if nx < 0
|| nx >= BOUNDARY
|| ny < 0
|| ny >= BOUNDARY
|| vis.contains(&(nx, ny))
|| block.contains(&(nx, ny))
{
continue;
}
queue.push_back((nx, ny));
vis.insert((nx, ny));
}
}

vis.len() >= MAX
}