1293. Shortest Path in a Grid with Obstacles Elimination

一題hard難度的題

簡單來說一樣用bfs, 但這個queue除了記下一個點, 他還得多記兩個資訊

一個是走過了多少路, 跟還剩下多少可以移除障礙的機會

然後用visited來記錄走過的點, 但這邊有一個問題是

假設visited已經被一個障礙用過了, 接著後面再被別人走到的可能還需要再走一遍嗎

用說的有點難理解, 我們舉一個例子

OOO
XXO
OOO
OXX
OOO

假設我先移除

OOO
*XO<- *表示被移除了
OOO
OXX
OOO

但我如果從另一邊走著走著

OOO
*XO
?OO<- 走到的點, 他還需要往上在移除這個障礙嗎？
OXX
OOO

可以發現, 當假設後面想要再來移除這個障礙, 其實就是有點雞肋, 前面的人早就移除並且往下走好幾步了, 所以當visited的數值 大於 你現在本身的數值, 然後你還要移除他在從算, 就有點多此一舉,

另外移除這個點的時候, 假設還剩三次機會, 結果你接下來只剩兩次機會, 並且還比較晚到, 那一定是不會更好

所以我們要先把他踢掉, 就不會一直做白工

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<vector<int>> q;
        q.push({0, 0, k, 0});
        vector<vector<int>> visited(m, vector<int>(n, -1));
        int res = 0;
        while(!q.empty()){
                auto cur = q.front();
                q.pop();
                if(cur[0] == m - 1 && cur[1] == n - 1) return cur[3];
                for(auto dir: dirs){
                    int x = dir[0] + cur[0];
                    int y = dir[1] + cur[1];
                    if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y] >= cur[2]){
                        continue;
                    }
                    if(grid[x][y] == 1){
                        if(cur[2] == 0){
                            continue;
                        }
                    }
                    q.push({x, y, grid[x][y] == 1?cur[2] - 1: cur[2], cur[3] + 1});
                    visited[x][y] = grid[x][y] == 1?cur[2] - 1: cur[2];
                }
        }
        return -1;
    }
};

時間複雜度 (M * N)