題目網址：https://leetcode.cn/problems/swim-in-rising-water/

題意： 在一個 n x n 的整數矩陣 grid 中, 每一個 grid[i][j] 表示位置 (i, j) 的平台高度。

當開始下雨時, 在時間為 t 時, 水池中的水位為 t。你可以從一個平台游向四周相鄰的任意平台, 前提是此時的水位必須同時淹沒這兩個平台才行。假設你可以瞬間移動無限距離, 也就是默認在 grid 內移動是不耗時的。

返回從左上角 (0, 0) 出發, 到達右下角 (n-1, n-1) 所需的最少時間。

Solution：

想法：利用 BFS + Min Heap, 把目前拜訪過的格子之鄰居（未拜訪過的）加入到 min heap pq 中, 然後每次取最小的出來, 直到抵達終點為止, 而 res 就是從 pq 取出過最大的高度

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        const int n = grid.size()
        int res = 0;
        vector<vector<bool>> visited(n, vector<bool>(n, false));

        using t3i = tuple<int, int, int>;
        priority_queue<t3i, vector<t3i>, greater<>> pq;
        pq.emplace(t3i{grid[0][0], 0, 0});

        while (!pq.empty()) {
            const auto [height, y, x] = pq.top();
            pq.pop();

            visited[y][x] = true;
            res = max(res, height); // 更新 res

            if (x == n - 1 && y == n - 1) {
                return res;
            }

            for (const auto& [yOffset, xOffset] : dirs) {
                const int newY = y + yOffset;
                const int newX = x + xOffset;

                // 若沒超過邊界, 且未拜訪, 則將其加到 pq 中
                if (!outOfBound(newY, newX, n) && !visited[newY][newX]) {
                    pq.emplace(t3i{grid[newY][newX], newY, newX});
                }
            }
        }
        return -1;
    }

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

    bool outOfBound(const int y, const int x, const int n){
        if (y < 0 || y >= n || x < 0 || x >= n) {
            return true;
        }
        return false;
    }
};
  • time：$O(n^2 \cdot log(n))$ ➔ pq 中最多有 $n^2$ 個元素, 每 push / pop 一個元素皆需花 $O(log(n^2))$
  • space：$O(n^2)$ ➔ visited、pq