[Python手撕]网格中的最短路径（可以有k次破墙的机会）

class Solution:
    def shortestPath(self, grid: List[List[int]], k: int) -> int:
        n = len(grid)
        m = len(grid[0])

        if m == n == 1:
            return 0

        direction = [[0, 1], [-1, 0], [1, 0], [0, -1]]
        visited = [[[False] * (k + 1) for _ in range(m)] for _ in range(n)]
        visited[0][0][k] = True
        queue = deque([(0, 0, k, 0)])

        while queue:
            x, y, f, s = queue.popleft()
            for d in direction:
                next_x = x + d[0]
                next_y = y + d[1]
                if next_x == n - 1 and next_y == m - 1:
                    return s + 1
                else:
                    # 判断下一个位置是否超出范围
                    if 0 <= next_x < n and 0 <= next_y < m:
                        # 如果下一个位置是墙，必须保证还有破墙术，
                        # 并且我们必须保证之前没有路径访问过这个位置的时候剩余的破墙数等于当前路径剩余的破墙术，
                        # 更不能容忍之前路径剩余的破墙术大于当前路径剩余的破墙术，
                        # 上面两种情况下，当前路径是不可能比之前路径更快的
                        if (
                            grid[next_x][next_y] == 1
                            and f >= 1
                            and sum(visited[next_x][next_y][f - 1 : k + 1]) == 0
                        ):
                            visited[next_x][next_y][f - 1] = 1
                            queue.append([next_x, next_y, f - 1, s + 1])
                        elif (
                            grid[next_x][next_y] == 0
                            and sum(visited[next_x][next_y][f : k + 1]) == 0
                        ):
                            visited[next_x][next_y][f] = 1
                            queue.append([next_x, next_y, f, s + 1])
        return -1