題目網址：https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/

題意：給一 m x n 的矩陣 grid, 其中每個 cell 不是 0（空）就是 1（障礙物）。每一步都可以在空白 cell 中上、下、左、右移動。

另給一整數 k, 代表最多可以消除 k 個障礙物。

返回從左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路徑長度。若找不到這樣的路徑, 則返回 -1。

Solution：

想法：看到走迷宮求最短路徑, 馬上想到 BFS。我們可以使用 (y, x, e) 代表一個搜索狀態, 其中 (y, x) 代表當前位置, e 代表當前消除障礙物的個數。此外, 我們還需用 visited 來記錄已拜訪的位置, 避免重複拜訪

  • 當 grid[i][j] == 1 時：若當前消除障礙物的個數 e 小於 k, 且 visited[i][j][e + 1] = false ➔ 可以選擇消除此障礙物, 並把 (i, j, e + 1) push 到 q 中
  • 當 grid[i][j] == 0 時：若 visited[i][j][e] = false ➔ 可以把 (i, j, e) push 到 q 中
typedef tuple<int, int, int> t3i;

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        m = grid.size(), n = grid[0].size();

        // 當 grid = [[0]], 即起點 = 終點時, 只需要 0 步
        if (m == 1 && n == 1) {
            return 0;
        }

        // 消除個數狀態有 k + 1 種（0 ~ k）
        visited.resize(m, vector<vector<bool>>(n, vector<bool>(k + 1, false)));

        queue<t3i> q;
        q.emplace(t3i{0, 0, 0});
        visited[0][0][0] = true;

        int step = 0;
        while (!q.empty()) {
            for (int len = q.size(); len > 0; --len) {
                const auto [y, x, e] = q.front();
                q.pop();

                for (const auto& [offsetY, offsetX] : dirs) {
                    const int i = y + offsetY;
                    const int j = x + offsetX;

                    // 若抵達終點, 則返回 step + 1（因為是下一步才到）
                    if (i == m - 1 && j == n - 1) {
                        return step + 1;
                    }

                    if (!outOfBound(i, j)) {
                        // 若為障礙物, 則可以選擇消除
                        if (grid[i][j] == 1) {
                            if (e == k) { // 如果消除個數已達上限, 則跳過
                                continue;
                            }

                            if (!visited[i][j][e + 1]) { // 若未拜訪, 則加到 q 中
                                visited[i][j][e + 1] = true;
                                q.emplace(t3i{i, j, e + 1});
                            }
                        } else {
                            if (!visited[i][j][e]) { // 若未拜訪, 則加到 q 中
                                visited[i][j][e] = true;
                                q.emplace(t3i{i, j, e});
                            }
                        }
                    }
                }
            }

            ++step;
        }

        return -1;
    }

private:
    int m, n;
    vector<pair<int, int>> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };
    vector<vector<vector<bool>>> visited;

    bool outOfBound(const int i, const int j){
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n \cdot k)$ ➔ q 中的元素個數不超過 m * n * k, for loop 最多執行 m * n * k 次
  • space：$O(m \cdot n \cdot k)$ ➔ visited