# 1036. Escape a Large Maze¶

• Time:
• Space:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { unordered_set blockedSet; for (const vector& b : blocked) blockedSet.insert(hash(b[0], b[1])); return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]), {}) && dfs(blockedSet, target[0], target[1], hash(source[0], source[1]), {}); } private: bool dfs(unordered_set& blockedSet, int i, int j, long target, unordered_set&& visited) { if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 || blockedSet.count(hash(i, j)) || visited.count(hash(i, j))) return false; visited.insert(hash(i, j)); if (visited.size() > (1 + 199) * 199 / 2 || hash(i, j) == target) return true; return dfs(blockedSet, i + 1, j, target, move(visited)) || dfs(blockedSet, i - 1, j, target, move(visited)) || dfs(blockedSet, i, j + 1, target, move(visited)) || dfs(blockedSet, i, j - 1, target, move(visited)); } long hash(int i, int j) { return (static_cast(i) << 16) + j; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) { Set blockedSet = new HashSet<>(); for (int[] b : blocked) blockedSet.add(hash(b[0], b[1])); return dfs(blockedSet, source[0], source[1], hash(target[0], target[1]), new HashSet<>()) && dfs(blockedSet, target[0], target[1], hash(source[0], source[1]), new HashSet<>()); } private boolean dfs(Set blockedSet, int i, int j, long target, Set visited) { if (i < 0 || i >= 1e6 || j < 0 || j >= 1e6 || blockedSet.contains(hash(i, j)) || visited.contains(hash(i, j))) return false; visited.add(hash(i, j)); if (visited.size() > (1 + 199) * 199 / 2 || hash(i, j) == target) return true; return // dfs(blockedSet, i + 1, j, target, visited) || // dfs(blockedSet, i - 1, j, target, visited) || // dfs(blockedSet, i, j + 1, target, visited) || // dfs(blockedSet, i, j - 1, target, visited); } private long hash(int i, int j) { return ((long) i << 16) + j; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution: def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool: def dfs(i: int, j: int, target: List[int], visited: set) -> bool: if not 0 <= i < 10**6 or not 0 <= j < 10**6 or (i, j) in blocked or (i, j) in visited: return False visited.add((i, j)) if len(visited) > (1 + 199) * 199 // 2 or [i, j] == target: return True return dfs(i + 1, j, target, visited) or \ dfs(i - 1, j, target, visited) or \ dfs(i, j + 1, target, visited) or \ dfs(i, j - 1, target, visited) blocked = set(tuple(b) for b in blocked) return dfs(source[0], source[1], target, set()) and dfs(target[0], target[1], source, set())