Leetcode 1036. Escape a Large Maze

Problem Explanation

In the given problem, we are given a large 2D grid of size 1 million by 1 million, and we are bound in this grid which means we can't walk outside the grid. Next, we are given a list of blocked squares in the grid that we can't walk on. Our goal is to start from a source square and reach a target square using the adjacent squares and without walking on the blocked squares. We can only walk to the 4-directionally adjacent squares that are up, down, right, or left to the current square. The location of each square in the grid is represented using coordinates (x, y) with 0 <= x, y < 10^6.

For instance, consider blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]. Starting from the source square [0, 0], we can't reach the target square [0, 2] because the square [0, 1] which is directly above the source square is blocked. Also, we can't go to the right square [1,0] because it is blocked. Hence, it is impossible to reach the target square starting from the source square in this case and the output of the function is false.

In this problem, the approach is to use Depth-First Search (DFS) to perform a search from the source to target and from target to source. If it's possible to reach from the source to the target and vice versa, we will return true. Otherwise, we will return false. DFS is a strategy that searches "deeper" in the graph whenever possible. DFS traverses the depth of any particular path before exploring its breadth. In DFS, we use a stack data structure for storing the visited nodes.

Python

1
2python
3 def dfs(blockedSet, i, j, target, visited):
4    if i < 0 or i >= 1e6 or j < 0 or j >= 1e6 or (i,j) in blockedSet or (i,j) in visited:
5      return False
6
7    visited.add((i, j))
8    if len(visited) > (1 + 199) * 199 / 2 or (i, j) == target:
9      return True
10    return dfs(blockedSet, i + 1, j, target, visited) or \
11           dfs(blockedSet, i - 1, j, target, visited) or \
12           dfs(blockedSet, i, j + 1, target, visited) or \
13           dfs(blockedSet, i, j - 1, target, visited)
14
15
16def isEscapePossible(blocked, source, target):
17    blockedSet = set(map(tuple, blocked))
18
19    return dfs(blockedSet, source[0], source[1], tuple(target), set()) and \
20           dfs(blockedSet, target[0], target[1], tuple(source), set())

Java

1
2java
3public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
4    Set<String> blockedSet = new HashSet<>();
5    Set<String> visited = new HashSet<>();
6
7    for (int[] point : blocked){
8        blockedSet.add(Arrays.toString(point));
9    }
10
11    return dfs(source, target, blockedSet, visited) && dfs(target, source, blockedSet, new HashSet<>());
12}
13
14private boolean dfs(int[] source, int[] target, Set<String> blocked, Set<String> visited){
15    if (outOfBound(source[0], source[1]) ||
16        blocked.contains(Arrays.toString(source)) ||
17        visited.contains(Arrays.toString(source))){
18        return false;
19    }
20
21    visited.add(Arrays.toString(source));
22
23    if ((visited.size() > 200 || Arrays.equals(source, target))){
24        return true;
25    }
26
27    for (int[] dir : dirs){
28        int next_x = source[0] + dir[0];
29        int next_y = source[1] + dir[1];
30        if(dfs(new int[]{next_x, next_y}, target, blocked, visited)){
31            return true;
32        }
33    }
34
35    return false;
36}
37
38private boolean outOfBound(int x, int y){
39    return x < 0 || x >= 1e6 || y < 0 || y >= 1e6;
40}

JavaScript

1
2javascript
3var isEscapePossible = function(blocked, source, target) {
4    let blockedSet = new Set();
5    for (let b of blocked){
6        blockedSet.add(hash(b));
7    }
8
9    return bfs(blockedSet, source, hash(target)) && bfs(blockedSet, target, hash(source)); 
10};
11
12function bfs(blocks, source, target){
13    let q = [source], seen = new Set(), cnt = 20000, move = [[0,1],[0,-1],[1,0],[-1,0]];
14    seen.add(hash(source));
15    while(q.length > 0){
16        let cur = q.shift();
17        if(hash(cur) === target)return true;
18        for(let m of move){
19            let x = cur[0]+m[0], y = cur[1]+m[1];
20            if(x < 0 || x >= 10**6 || y < 0 || y >= 10**6 || blocks.has(hash([x,y])) || seen.has(hash([x,y])))continue;
21            q.push([x,y]);
22            seen.add(hash([x,y]));
23            if(cnt-- <= 0)return true;
24        }
25    }
26    return false;
27}
28
29function hash(pos){
30    return pos[0] * 1000000 + pos[1];
31}

All three solutions use the same logic to solve the problem, with some differences in how they iterate over neighboring nodes and handle blocked squares. The Python solution uses recursion and a set data structure to store blocked squares and visited squares. The Java solution uses a similar approach and additionally includes a helper method to check if a given square is out of bounds.

The JavaScript solution uses BFS (Breadth-First Search) instead of DFS. Where DFS explores as far as possible along each branch before backtracking, BFS explores the neighbor nodes at the present depth before moving on to nodes at the next depth level. Although BFS could potentially inspect more nodes than DFS, both algorithms are suitable for this problem, as they will both eventually cover all reachable squares in the grid.

The key point is that rather than simply determining whether the target can be reached from the source, these solutions also check if the source can be reached from the target. This is to ensure that the path is not a one-way route where the target can be reached from the source but not the other way around.

The solutions also ensure that the same square is not visited multiple times, which is important for avoiding infinite loops. This is achieved by storing visited squares in a set. For an efficient lookup operation, the solutions convert to the coordinates to string format or use a hashing function to represent coordinates in the blocked set and the visited set.

In terms of space and time complexity: These solutions achieve O(B) space where B is the length of the blocked list (since all blocked nodes are saved in the blocked set) and a time complexity of O(min(B, ((B/N)^2), where N is the number of moves around the source or target, this is because in worst case it will move around the source and target until all block or max move count is reached. The min function is used here because the time complexity will always be the smallest among these conditions.