from collections import deque
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
# Base Case
m, n = len(grid), len(grid[0])
if m==1 and n==1:
return 0
# Prepare
d = [(1,0),(-1,0),(0,1),(0,-1)]
in_bound = lambda x,y: 0<=x<m and 0<=y<n
step = 0
# BFS - start at the 0,0,k
q = deque()
q.append((0,0,k))
visited = set()
visited.add((0,0,k))
while q:
size = len(q)
step +=1
for _ in range(size):
i, j, curr_k = q.popleft()
for k in range(4):
x = i + d[k][0]
y = j + d[k][1]
if in_bound(x,y) and x == m-1 and y == n-1:
return step
# Check the empty cell can move
if in_bound(x,y) and curr_k >= 0 and (x,y, curr_k) not in visited and grid[x][y] == 0:
q.append((x,y,curr_k))
visited.add((x,y,curr_k))
# Check the obstacle cell can move
if in_bound(x,y) and curr_k-1 >= 0 and (x,y,curr_k-1) not in visited and grid[x][y] == 1:
q.append((x,y,curr_k-1))
visited.add((x,y,curr_k-1))
return -1