Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1036.html
1036. Escape a Large Maze
Level
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:
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
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++) blockedSet.add(Arrays.toString(blocked[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>(); visitedSet.add(Arrays.toString(source)); int visitedCount = 1; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; Queue<int[]> queue = new LinkedList<int[]>(); 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)) { if (visitedSet.add(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 seen.add((x, y)) 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 seen.add((x, y)) 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 }