LC 1730 [M] Shortest Path to Get Food - ALawliet/algorithms GitHub Wiki
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
ROWS = len(grid)
COLS = len(grid[0])
# Our four permitted directions.
DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
# Find the starting position and add to the queue.
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '*':
Q.append((r, c, 0))
break
while Q:
r, c, steps = Q.popleft()
for dr, dc in DIRS:
nr = r + dr
nc = c + dc
# Ensure that the new row and col is in the grid and an unvisited or food node.
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] != 'X': # in ('O','#')
# We found food, we're done.
if grid[nr][nc] == '#':
return steps + 1
# Mark as visited so we don't visit again.
grid[nr][nc] = 'X'
Q.append((nr, nc, steps + 1))
# We ran out of locations and found no food.
return -1