(Leetcode) Escape a large maze

Question

This is a Leetcode problem -

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 <= 200
• blocked[i].length == 2
• 0 <= blocked[i][j] < \$10^6\$
• source.length == target.length == 2
• 0 <= source[i][j], target[i][j] < \$10^6\$
• source != target

Here is my solution to this challenge -

from collections import deque

# Bidirectional BFS

def is_escape_possible(blocked: List[List[int]], source: List[int], target: List[int]) -> bool:

    if len(blocked) < 2:
        return True
    n = 10 ** 6
    block_set = set(map(tuple, blocked))

    #initialize two deque

    bfs_que_s = deque([tuple(source)])
    bfs_que_t = deque([tuple(target)])

    # visited sets for the two points

    visited_s = set([tuple(source)])
    visited_t = set([tuple(target)])

    # wave set means the outline of BFS

    wave_s = set([tuple(source)])
    wave_t = set([tuple(target)])

    # BFS into the next layer, if the current queue is empty, return False, which means this point is sealed by blocks

    def bfs_next(bfs_que, visited, wave):
        size = len(bfs_que)
        if not size:
            return False
        wave.clear()
        for _ in range(size):
            c_r, c_c = bfs_que.popleft()
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                n_r = c_r + dx
                n_c = c_c + dy
                if 0 <= n_r < n and 0 <= n_c < n and (n_r, n_c) not in block_set and (n_r, n_c) not in visited:
                    bfs_que.append((n_r, n_c))
                    visited.add((n_r, n_c))
                    wave.add((n_r, n_c))
        return True

    # mark the points have escaped or not

    escape_s = False
    escape_t = False

    # when waves share some same values, they met in the search, return True

    while not wave_s & wave_t:
        if not escape_s:
            if not bfs_next(bfs_que_s, visited_s, wave_s):
                return False

            # when wave's length > blocks' length, the point must have escaped the blocks

            if len(wave_s) > len(blocked):
                escape_s = True
        if not escape_t:
            if not bfs_next(bfs_que_t, visited_t, wave_t):
                return False
            if len(wave_t) > len(blocked):
                escape_t = True

        #both of the points are escaped

        if escape_s and escape_t:
            return True
    return True

Here is my idea of the challenge -

If we conduct two independent searches to find out whether either of the two points is blocked or not, we may search for many duplicated and unnecessary points in the case that two points can reach each other. So we can start BFS from both directions simultaneously, one layer frontward and one layer backward; when they meet, we can return True.

Here is my Leetcode result -

So, I would like to know whether I could make this program shorter and more efficient.

Answer 1

Without leaking the better algorithm, I'll highlight one area where this code can be dramatically improved.

You are ignoring a pair of important facts:

• 0 <= len(blocked) <= 200
• 0 <= blocked[i][j] < \$10^6\$

Pigeonhole principle: if you have more holes than pigeons, some holes will be empty. On your grid, you have at least 999800 rows that will be empty, and at least 999800 columns that will be empty. Using a BFS wave that traverses the grid space can result in taking a lot of steps which can be optimized away.

x_min = min(block[0] for block in blocked)
x_max = max(block[0] for block in blocked)
y_min = min(block[1] for block in blocked)
y_max = max(block[1] for block in blocked)

The above will quickly determine the bounds of all blocked cells.

                                 :
                                 0
            x_min                :                x_max
          0|0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0
          -+-------------------------------------------+-
          0|0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0|0 y_min
          0|1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0|0
... 0 ... 0|0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0|0 ... 0 ...
          0|0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1|0
          0|0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0|0
          0|0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0|0 y_min
          -+-------------------------------------------+-
          0|0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0|0
                                 :
                                 0
                                 :

If your starting point is to the left of x_min, or above y_min, or to the right of x_max, or below y_max, and your target point is to the left of x_min, or above y_min, or to the right of x_max, or below y_max then the path cannot be blocked. Fast succeed for the trivial cases, verses the wave propagation which might have to create a wavefront from one side of the grid to the other.

But wait! It is possible for [0,0] and [999999,999999] to both be in blocked which makes the bounding box [[x_min, y_min], [x_max, y_max]] encompass the entire grid.

Again, by the pigeon hole principle, with only 200 blocked grid spots, if x_max - x_min + 1 > 200, there will be a column in between those limits which is completely unblocked. Similarly, if y_max - y_min + 1 > 200, there will be a row in between those limits which is completely unblocked. Either one will allow you to subdivide the grid into two (or more) bounding boxes whose sides are less than 200 cells in length. In the above figure, you could divide the region into two sub regions: one 12 cells wide and the other 5 cells wide. After partitioning, the left region becomes 12x5 and the right region is 5x4. If the starting point and the target point are both outside of all bounding boxes, then the path cannot be blocked.

If either, or both, of the path end points are within a blocked bounding box, you can use your BFS wavefront to attempt to escape the bounding box. If both end points can escape, the path is not blocked. If both path end points are within the same bounding box, then if the wavefronts meet, then the path is not blocked. In any case, your BFS wavefront algorithm need only operate in at most a 200x200 grid area, not the entire \$10^6 x 10^6\$ problem grid.

Answer 2

There are few redundancies, both time and memory wise.

• You don't need to maintain an entire visited set. It is only necessary for a general graph. For the grid, the wave computed at the previous iteration serves equally good.

• Upon completion of bfs_next, both wave and bfs_que contain the same set of points. You don't need to update wave in the loop. Do wave = set(bfs_que) once, after the loop terminates. Since set is a built-in primitive, this should run faster.

• I am not sure that dequeue is a right tool. The for _ in range(size) loop effectively drains it every time, and there is no need to store the new wavefront in the same structure with the old one. Consider using two lists instead.

Also, for the clarity of the algorithm, I'd seriously consider reworking bfs_next into a generator, yielding the next wavefront.

---

All that said, I am not convinced that len(wave) > len(blocked) means escape. In fact, correct me if I am wrong, when 9 blockers cut off the corner

   |*
   | *
   |  *
   |  3*
   | 323*
   |32123*
   |210123*
   |32123  *
   | 323    *
   +----------

the length of the third wavefront is 10. However, there is no escape.