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:

  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++)
                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
    }
    
    

All Problems

All Solutions