題目網址：https://leetcode.cn/problems/pacific-atlantic-water-flow/

題意：今有一 m x n 矩形島嶼, 與太平洋和大西洋相鄰。

  • 太平洋位於島嶼的左邊界和上邊界
  • 大西洋位於島嶼的右邊界和下邊界

給一 m x n 整數 array heights, 其中 heights[r][c] 代表座標 (r, c) 高於海平面的高度

相鄰 cell 的高度 小於或等於 目前 cell 的高度, 則雨水可以直接流向相鄰 cell

求哪些位置的雨水能同時流進太平洋和大西洋？

Solution 1：

想法：利用 DFS, 從邊界開始往內陸行進, 若高度越來越高則代表水可往邊界流, 藉此可找到抵達太平洋和大西洋的兩個集合, 然後取交集

  • 最左和最上的邊界一定能抵達太平洋（由這兩邊界向內延伸）
  • 最右和最下的邊界一定能抵達大西洋（由這兩邊界向內延伸）

typedef pair<int, int> pii;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n, false));
        vector<vector<bool>> atl(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            bfs(heights, i, 0, pac); // left
            bfs(heights, i, n - 1, atl); // right
        }

        for (int j = 0; j < n; ++j) {
            bfs(heights, 0, j, pac); // top
            bfs(heights, m - 1, j, atl); // bottom
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pac[i][j] && atl[i][j]) {
                    res.emplace_back(vector<int>{i, j});
                }
            }
        }
        return res;
    }

private:
    int m, n;
    vector<vector<int>> res;
    queue<pii> q;
    vector<pii> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void bfs(vector<vector<int>>& h, const int i, const int j, vector<vector<bool>>& visited){
        q.emplace(pii{i, j});

        while (!q.empty()) {
            const auto [y, x] = q.front();
            q.pop();

            if (visited[y][x]) {
                continue;
            }

            visited[y][x] = true;

            for (const auto& [dirY, dirX] : dirs) {
                const int r = y + dirY, c = x + dirX;
                if (!outOfBound(r, c) && h[y][x] <= h[r][c] && !visited[r][c]) {
                    q.emplace(pii{r, c});
                }
            }
        }
    }

    bool outOfBound(const int r, const int c){
        if (r < 0 || r == m || c < 0 || c == n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n)$ ➔ 每個 node 最多被訪問四次（來自上下左右的鄰居）
  • space：$O(m \cdot n)$ ➔ pac, atl

Solution 2：

想法：利用 BFS, 想法同 Solution 1

typedef pair<int, int> pii;

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n, false));
        vector<vector<bool>> atl(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            bfs(heights, i, 0, pac); // left
            bfs(heights, i, n - 1, atl); // right
        }

        for (int j = 0; j < n; ++j) {
            bfs(heights, 0, j, pac); // top
            bfs(heights, m - 1, j, atl); // bottom
        }

        vector<vector<int>> res;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pac[i][j] && atl[i][j]) {
                    res.emplace_back(vector<int>{i, j});
                }
            }
        }
        return res;
    }

private:
    int m, n;
    queue<pii> q;
    vector<pii> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void bfs(vector<vector<int>>& h, const int i, const int j, vector<vector<bool>>& visited){
        q.emplace(pii{i, j});

        while (!q.empty()) {
            const auto [y, x] = q.front();
            q.pop();

            if (outOfBound(y, x) || visited[y][x]) {
                continue;
            }

            visited[y][x] = true;

            for (const auto& [dirY, dirX] : dirs) {
                const int r = y + dirY, c = x + dirX;
                if (!outOfBound(r, c) && h[y][x] <= h[r][c]) {
                    q.emplace(pii{r, c});
                }
            }
        }
    }

    bool outOfBound(const int r, const int c){
        if (r < 0 || r == m || c < 0 || c == n) {
            return true;
        }
        return false;
    }
};
  • time：$O(m \cdot n)$ ➔ 每個 node 最多被訪問四次（來自上下左右的鄰居）
  • space：$O(m \cdot n)$ ➔ pac, atl