LC 1926 [M] Nearest Exit from Entrance in Maze - ALawliet/algorithms GitHub Wiki
DIRS = [1, 0, -1, 0, 1]
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
er, ec = entrance
n_rows, n_cols = len(maze), len(maze[0])
Q = deque([ (er, ec, 0) ])
while Q:
r, c, path_len = Q.popleft()
if (not r==er or not c==ec) and (r==0 or c==0 or r==n_rows-1 or c==n_cols-1): # not entrance and border
return path_len
for i in range(4):
nr, nc = r+DIRS[i], c+DIRS[i+1]
if nr<0 or nc<0 or nr==n_rows or nc==n_cols or maze[nr][nc]=='+': continue
Q.append( (nr, nc, path_len+1) )
maze[nr][nc] = '+' # mark visited with another wall
return -1