This is a Leetcode problem -
In a 1 million by 1 million grid, the coordinates of each grid square are
(x, y)with \$0\$ \$<=\$
We start at the
sourcesquare and want to reach the
targetsquare. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of
Trueif 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.
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
Here is my Leetcode result -
So, I would like to know whether I could make this program shorter and more efficient.