1036. Escape a Large Maze

Comments

Problem Setting

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

Link for Problem: leetcode

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.

Solution from badgergo

In [5]:
import collections
from typing import List, Set, Dict, Tuple, Optional
class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        blocked = {(x, y) for x, y in blocked}
        source = tuple(source)
        target = tuple(target)
        def bfs(s, e):
            visited = {s}
            frontier = collections.deque([s])
            while frontier:
                sz = len(frontier)
                if sz > len(blocked) * 4:
                    return 1
                for i in range(sz):
                    r, c = frontier.popleft()
                    if (r, c) == e:
                        return 2
                    for newr, newc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
                        if 0 <= newr < 1000000 and 0 <= newc < 1000000 and (newr, newc) not in blocked and (newr, newc) not in visited:
                            visited.add((newr, newc))
                            frontier.append((newr, newc))
            return 0
        return bfs(source, target) + bfs(target, source) > 1
In [10]:
# Example 1
blocked = [[0,1],[1,0]]; source = [0,0]; target = [0,2]
s = Solution()
s.isEscapePossible(blocked, source, target)
Out[10]:
False

Step-by-step understanding

This problem can be solved by using dynamic programming. Overall flow is as blew:

  1. Initial setting
  2. Define recursive function bfs for dynamic programming
  3. Execute the recursive function from the starting point i.e., source to the end point i.e. target as well as the other way around i.e., from target to source

Initial setting

L5-7 convert input arguments into tuple format.

In [11]:
print('Before: ', blocked, source, target)
blocked = {(x, y) for x, y in blocked}
source = tuple(source)
target = tuple(target)
print('After: ', blocked, source, target)

Before:  [[0, 1], [1, 0]] [0, 0] [0, 2]
After:  {(0, 1), (1, 0)} (0, 0) (0, 2)

Define dfs

This recursive function explore the 1 million by 1 million grid using DFS (Depth First Search), in which a recursive function goes deeper search areas first until it reaches a sort of the end.

In [13]:
def bfs(s, e):
    visited = {s}
    frontier = collections.deque([s])
    while frontier:
        sz = len(frontier)
        if sz > len(blocked) * 4:
            return 1
        for i in range(sz):
            r, c = frontier.popleft()
            if (r, c) == e:
                return 2
            for newr, newc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
                if 0 <= newr < 1000000 and 0 <= newc < 1000000 and (newr, newc) not in blocked and (newr, newc) not in visited:
                    visited.add((newr, newc))
                    frontier.append((newr, newc))
    return 0
  • visited keeps tracking where it is already searched.
  • frontier keeps tracking the grid coordinates it needs to check.
In [16]:
s = source; e = target

visited = {s}
frontier = collections.deque([s])
while frontier:
    sz = len(frontier)
    if sz > len(blocked) * 4:
        pass
#         return 1
    for i in range(sz):
        r, c = frontier.popleft()
        if (r, c) == e:
            pass
#             return 2
        for newr, newc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
            if 0 <= newr < 1000000 and 0 <= newc < 1000000 and (newr, newc) not in blocked and (newr, newc) not in visited:
                visited.add((newr, newc))
                frontier.append((newr, newc))
    break
In [22]:
print(visited, frontier, sz, len(blocked))

{(0, 0)} deque([]) 1 2

Check a 4-directionally adjacent square

There are 4 different direction that we can move. The if statement checks the followings:

  • the next point is within the grid (make sure that it is not out of indexes.)
  • the next point is not in the blocked list
  • the next point is not in the visited list

If all three conditions are met, it adds the next points (newr, newc) to visited. Also, it appends the next points are frontier

for newr, newc in (r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1):
    if 0 <= newr < 1000000 and 0 <= newc < 1000000 and
    (newr, newc) not in blocked and
    (newr, newc) not in visited:

        visited.add((newr, newc))
        frontier.append((newr, newc))

Check if one of the frontiers reaches the end e

In the for loop, it takes one coordinate (r, c) from frontier and check if it matches with e, the end destination.

for i in range(sz):
    r, c = frontier.popleft()
    if (r, c) == e:
        return 2

Execute dfs from both source and target

By executing the dfs from both source and target, if it meets on the same coordinate, it means it is solved.

return bfs(source, target) + bfs(target, source) > 1

Comments

Comments powered by Disqus