Leetcode1293.网格中的最短路径

曾经终败给现在 2022-12-17 14:50 10阅读 0赞

给你一个 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)。

struct triple {
        
        int x, y;
        int rest;
        triple(int _x, int _y, int _r): x(_x), y(_y), rest(_r) {
        }
    };
    
    
    class Solution {
        
    public:
        int shortestPath(vector<vector<int>>& grid, int k) {
        
            static int dirs[4][2] = {
        {
        -1, 0}, {
        1, 0}, {
        0, -1}, {
        0, 1}};
            int m = grid.size(), n = grid[0].size();
            if(m==1 && n==1)return 0;
            k = min(m + n - 3, k);
            bool visited[m][n][k+1];
            memset(visited, false, sizeof(visited));
            queue<triple> q;
            q.emplace(0, 0, k);
            visited[0][0][k] = true;
    
            for(int step = 1; q.size() > 0; ++step){
        
                int cnt = q.size();
                for(int _ = 0; _ < cnt; ++_){
        
                    triple cur = q.front();
                    q.pop();
                    for(int d = 0; d < 4; ++d){
        
                        int x = cur.x + dirs[d][0], y = cur.y + dirs[d][1];
                        if(x >=0 && x < m && y >= 0 && y < n){
        
                            if(grid[x][y] == 0 && !visited[x][y][cur.rest]){
        
                                if(x == m - 1 && y == n - 1)return step;
                                q.emplace(x, y, cur.rest);
                                visited[x][y][cur.rest] = true;
                            }else if(grid[x][y] == 1 && cur.rest > 0 && !visited[x][y][cur.rest - 1] ){
        
                                q.emplace(x, y, cur.rest - 1);
                                visited[x][y][cur.rest - 1] = true;
                            }
                        }
    
                    }
                }
            }
            return -1;
            
        }
    };