(Leetcode) Escape a large maze This is a Leetcode problem -


  In a 1 million by 1 million grid, the coordinates of each grid square
  are (x, y) with \$0\$ \$&lt;=\$ x\$,\$ y \$&lt;\$ \$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 &lt;= blocked.length &lt;= 200
  blocked[i].length == 2
  0 &lt;= blocked[i][j] &lt; \$10^6\$
  source.length == target.length == 2
  0 &lt;= source[i][j], target[i][j] &lt; \$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]) -&gt; bool:

    if len(blocked) &lt; 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 &lt;= n_r &lt; n and 0 &lt;= n_c &lt; 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 &amp; wave_t:
        if not escape_s:
            if not bfs_next(bfs_que_s, visited_s, wave_s):
                return False

            # when wave's length &gt; blocks' length, the point must have escaped the blocks

            if len(wave_s) &gt; 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) &gt; 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.
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) &gt; 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.