use BFS to record each node and its distance from entry
you cannot consume all the nodes in queue all at once, since the visited won't be updated right after each node traverse.
take entrance point in queue
search the four directions, if it can_go, record the dist + 1 and the node position
keep traverse, once found the exit, return the dist
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
def out_of_index(i, j, m, n):
return i < 0 or i >= m or j < 0 or j >= n
def is_exit(i, j, m, n):
return i in [0, m - 1] or j in [0, n - 1]
queue = [(entrance[0], entrance[1], 0)]
m, n = len(maze), len(maze[0])
visited = set()
visited.add((entrance[0], entrance[1]))
directions = [(1,0), (0,1), (-1,0), (0,-1)]
while queue:
row, col, dist = queue.pop(0)
if is_exit(row, col, m, n) and dist != 0:
return dist
for i, j in directions:
new_row, new_col = row + i, col + j
if out_of_index(new_row, new_col, m, n):
continue
new_cell = maze[new_row][new_col]
if new_cell == '.' and (new_row, new_col) not in visited:
visited.add((new_row, new_col))
queue.append((new_row, new_col, dist + 1))
return -1
use BFS to record each node and its distance from entry you cannot consume all the nodes in queue all at once, since the visited won't be updated right after each node traverse.