1293. 网格中的最短路径

原题链接

思路

玩家移动中可以消除 \(k\) 个障碍物，对于最短路，同一个点不会经过超过两次，因此消除 \(k\) 个障碍物可以看成经过 \(k\) 个障碍物。

所以可以维护一个三元组 \((x,y,r)\)，表示搜索状态从 \((0,0)\) 这个点到达 \((x,y)\) 这个点经过了 \(r\) 个障碍物。

通过宽搜即可搜索出最短路径长度。

代码

class Solution {
public:
    struct Point {
        int x, y, rect, step;
    };

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

    int shortestPath(vector<vector<int>>& grid, int k) {
        int n = grid.size();
        int m = grid[0].size();
        if (n == 1 && m == 1) return 0;
        k = min(k, n + m - 3);

        bool st[n][m][k + 1];
        memset(st, false, sizeof st);

        queue<Point> q;
        q.push({0, 0, k, 0});
        st[0][0][k] = true;

        while (q.size()) {
            auto [x, y, r, step] = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (grid[nx][ny] == 0 && !st[nx][ny][r]) {
                    if (nx == n - 1 && ny == m - 1) return step + 1;
                    q.push({nx, ny, r, step + 1});
                    st[nx][ny][r] = true;
                } else if (grid[nx][ny] == 1 && r > 0 && !st[nx][ny][r - 1]) {
                    q.push({nx, ny, r - 1, step + 1});
                    st[nx][ny][r - 1] = true;
                }
            }
        }
        return -1;
    }
};