网格中的最短路径

这题解使用了宽度优先搜索（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