1293. Shortest Path in a Grid with Obstacles Elimination

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: Array、Breadth-First Search、Matrix

一、題目

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacles). You can move up, down, left, or right from and to an empty cell in one step.
Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right conrer m-1, n-1 given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:
short1-grid

  • Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
  • Output: 6
  • Explanation:
    The shortest path without eliminating any obstacle is 10.
    The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2: short2-grid

  • Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
  • Output: -1
  • Explanation:
    We need to eliminate at least two obstacles to find such a walk.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 40
  • 1 <= k <= m * n
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

二、分析

  • 本題可以搭配 BFS，最早滿足終止條件時，回傳即為最短路徑。
  • 由於本題並非可以單純的藉 visited 來記錄是否拜訪過，因為多了一個變數 k，所以在此可以將 vector<vector<bool>> visited 換成 vector<vector<int>> visited，並將記錄的值改成剩餘可消除障礙物的次數，依 greedy 的想法，在走同樣的距離下，剩餘可消除障礙物的次數愈多愈好，故我們可將拜訪過，但「剩餘次數少於或等於 visited[row][col]」的節點跳過。

三、解題

1. BFS

  • Time complexity: \(O(m\times n\times k)\)
  • Space complexity: \(O(m\times n)\)
int dirc[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> visited(m, vector<int>(n, -1));  // 餘愈多愈好，故預設為 -1
    queue<vector<int>> q; // {row, col, len, k}
    q.push({0,0,0,k});
    
    while (!q.empty()) {
        auto info = q.front();
        q.pop();
        int row = info[0];
        int col = info[1];
        int len = info[2];
        int bomb = info[3];
        
        // 超出範圍 out of bound
        if (row < 0 || col < 0 || row >= m || col >= n) continue;
        
        // 終止條件，到達右下角 
        if (row == m-1 && col == n-1) return len;
        
        // 遇到障礙物
        if (grid[row][col] == 1) {
            if (bomb > 0) 
                bomb--;
            else 
                continue;
        }
        
        // 減枝：拜訪過且剩餘次數較少者跳過
        if (visited[row][col] >= bomb) continue;
        visited[row][col] = bomb;
        
        // 將下一步加入佇列
        for (const auto& d : dirc){
            q.push({row+d[0], col+d[1], len+1, bomb});
        }
    }
    return -1;
}

回目錄 Catalog