题目描述

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。

样例

输入： 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6。
该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2)。

输入：
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。

限制

• grid.length == m
• grid[0].length == n
• 1 <= m, n <= 40
• 1 <= k <= m*n
• grid[i][j] == 0 或 1
• grid[0][0] == grid[m-1][n-1] == 0

算法

(宽度优先搜索 / BFS) $O(mnk)$

1. 由于求的是最短路问题，所以适合用宽搜求解。
2. 宽搜的状态从二维扩展到三维，前两维记录坐标，最后一维记录下消除障碍的个数。
3. 每次扩展四个方向，如果新扩展的位置有障碍，则转移时注意判断消除障碍的个数是否不超过 k 个。
4. 宽搜的过程中如果二维坐标到达了终点，则直接返回结果。

时间复杂度

• 总共有 $O(mnk)$ 个状态，每个状态最多遍历一次，故时间复杂度为 $O(mnk)$。

空间复杂度

• 总共有 $O(mnk)$ 个状态，需要 $O(mnk)$ 的空间记录每个状态到起点的距离，队列也需要 $O(mnk)$ 的空间。
• 故总空间复杂度为 $O(mnk)$。

C++ 代码

struct Node {
    int x, y, k;
    Node(){}
    Node(int x_, int y_, int k_): x(x_), y(y_), k(k_){};
};

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        const int INF = m * n;
        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {1, 0, -1, 0};
        vector<vector<vector<int>>> dis(
            m,
            vector<vector<int>>(n, vector<int>(m * n + 1, INF)));
        queue<Node> q;

        q.push(Node(0, 0, 0));
        dis[0][0][0] = 0;

        while (!q.empty()) {
            Node sta = q.front();
            if (sta.x == m - 1 && sta.y == n - 1)
                return dis[sta.x][sta.y][sta.k];

            q.pop();
            for (int i = 0; i < 4; i++) {
                int tx = sta.x + dx[i], ty = sta.y + dy[i];
                if (tx < 0 || tx >= m || ty < 0 || ty >= n)
                    continue;
                if (grid[tx][ty] == 1) {
                    if (sta.k < k
                     && dis[tx][ty][sta.k + 1] > dis[sta.x][sta.y][sta.k] + 1) {
                        dis[tx][ty][sta.k + 1] = dis[sta.x][sta.y][sta.k] + 1;
                        q.push(Node(tx, ty, sta.k + 1));
                    }
                } else {
                    if (dis[tx][ty][sta.k] > dis[sta.x][sta.y][sta.k] + 1) {
                        dis[tx][ty][sta.k] = dis[sta.x][sta.y][sta.k] + 1;
                        q.push(Node(tx, ty, sta.k));
                    }
                }
            }
        }

        return -1;
    }
};