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 <= 200blocked[i].length == 20 <= blocked[i][j] < 10^6source.length == target.length == 20 <= source[i][j], target[i][j] < 10^6source != 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 }