1 题目：1293. 网格中的最短路径

官方标定难度：难

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

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

示例 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

2 solution

采用广度优先算法
$$step{s}_{ijk}:i,j处消除了k个障碍的最小步数$$

代码

class Solution {
    /*
     * dp[i][j][k]
     *
     */
public:
    int shortestPath(vector<vector<int>> &grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        if (m * n == 1) return 0;

        vector<vector<vector<int>>> steps(m, vector<vector<int>>(n, vector<int>(k + 1, -1)));
        queue<int> row, col, cle;
        steps[0][0][0] = 0;
        row.push(0), col.push(0), cle.push(0);

        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};

        while (!row.empty()) {
            int i = row.front();
            int j = col.front();
            int t = cle.front();
            row.pop(), col.pop(), cle.pop();
            for (int ii = 0; ii < 4; ii++) {
                int r = i + dx[ii];
                int c = j + dy[ii];
                if (r < 0 || r == m || c < 0 || c == n) continue;

                if (grid[r][c]) {
                    if (t == k) continue;
                    if( steps[r][c][t + 1] == -1) {
                        steps[r][c][t + 1] = steps[i][j][t] + 1;
                        row.push(r);
                        col.push(c);
                        cle.push(t + 1);
                    }
                } else {
                    if( steps[r][c][t] == -1) {
                        steps[r][c][t] = steps[i][j][t] + 1;
                        row.push(r);
                        col.push(c);
                        cle.push(t);
                    }
                }

                if (r == m - 1 && c == n - 1) return steps[i][j][t] + 1;
            }
        }
        return -1;
    }
};

结果