1293. Shortest Path with Obstacles Elimination

https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/

01矩阵上0能走，1不能，问在最多消除k个1的条件下，从(0, 0)到(M - 1, N - 1)的最短距离。图上最短距离=>BFS。每步限制是消除的数目不能超过k，因此用类似DP的思想把限制encoding进状态，让visited记录到(i, j)至少需要消除多少个1。

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        const int M = grid.size(), N = M == 0 ? 0 : grid[0].size();
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<vector<int>> q;
        q.push({0, 0});
        vector<vector<int>> visited(M, vector<int>(N, k + 1));
        visited[0][0] = grid[0][0] == 1 ? 1 : 0;
        for (int step = 0; !q.empty(); ++step) {
            for (int size = q.size(); size > 0; --size) {
                const auto &t = q.front();
                int i = t[0], j = t[1];
                if (i == M - 1 && j == N - 1) return step;
                for (const auto &d : dirs) {
                    int r = i + d[0], c = j + d[1];
                    if (r >= 0 && r < M && c >= 0 && c < N && visited[r][c] > visited[i][j]) {
                        if (grid[r][c] == 1 && visited[i][j] == k) continue;
                        visited[r][c] = visited[i][j] + (grid[r][c] == 1 ? 1 : 0);
                        q.push({r, c});
                    }
                }
                q.pop();
            }
        }
        return -1;
    }
};