这题解使用了宽度优先搜索(BFS)来找到从网格的左上角到右下角的最短路径。这里的关键是可以选择消除最多k个障碍物。为了处理这个条件,搜索状态不仅包括当前位置坐标 (x, y),还包括一个剩余障碍物消除次数 `rest`。状态被保存在一个队列中,每个状态为 (x, y, rest),其中 `rest` 表示还可以消除的障碍物数量。为防止重复处理相同的状态,使用一个集合 `visited` 来记录已经访问过的状态。搜索过程中,对于每个状态,都尝试向四个方向移动,如果是空白格并且该状态未被访问,则将其加入队列;如果是障碍物且 `rest` 大于0,则消除障碍物并将新状态加入队列。如果能到达终点,则返回当前步数。
时间复杂度: O(m*n*k)
空间复杂度: O(m*n*k)
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
if len(grid) == 0 or len(grid[0]) == 0:
return 0 # 如果网格为空,直接返回0
m = len(grid)
n = len(grid[0])
if k >= m + n - 3:
return m + n - 2 # 如果可以移除的障碍物足够多,直接走最短路径
dx = [(0, 1), (0, -1), (-1, 0), (1, 0)] # 方向数组
visited = set((0,0,k)) # 访问集合
q = deque([(0,0,k)]) # BFS 队列
step = 0
while q:
size = len(q)
step += 1
for i in range(size):
x, y, rest = q.popleft()
for d in dx:
nx = x + d[0]
ny = y + d[1]
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue # 越界检查
if grid[nx][ny] == 0 and (nx, ny, rest) not in visited:
if nx == m - 1 and ny == n - 1:
return step # 如果到达终点,返回步数
q.append((nx, ny, rest)) # 加入新状态
visited.add((nx, ny, rest))
elif grid[nx][ny] == 1 and rest > 0 and (nx, ny, rest - 1) not in visited:
q.append((nx, ny, rest-1)) # 消除障碍物并加入新状态
visited.add((nx, ny, rest-1))
return -1 # 如果无法到达终点,返回-1