LC 1293 [H] Shortest Path in a Grid with Obstacles Elimination - ALawliet/algorithms GitHub Wiki
DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
n_rows = len(grid)
n_cols = len(grid[0])
# 1x1 edge case
if n_rows == 1 and n_cols == 1:
return 0
Q = deque([ (0, 0, 0, 0) ]) # r, c, obstacle count, path len
visited = set()
while Q:
r, c, obstacles_smashed, path_len = Q.popleft()
if (r, c) == (n_rows - 1, n_cols - 1):
return path_len
for dr, dc in DIRS:
nr = r + dr
nc = c + dc
if 0 <= nr < n_rows and 0 <= nc < n_cols:
# we can potentially queue 2 states per direction
# there is an obstacle and we have enough to smash it
if grid[nr][nc] == 1 and obstacles_smashed < k and (nr, nc, obstacles_smashed + 1) not in visited:
Q.append( (nr, nc, obstacles_smashed + 1, path_len + 1) )
visited.add( (nr, nc, obstacles_smashed + 1) )
# there is no obstacle and we just take the open space
if grid[nr][nc] == 0 and (nr, nc, obstacles_smashed) not in visited:
Q.append( (nr, nc, obstacles_smashed, path_len + 1) )
visited.add( (nr, nc, obstacles_smashed) )
return -1