Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 417. Pacific Atlantic Water Flow

---

參考資訊：
https://www.cnblogs.com/grandyang/p/5962508.html

題目：


解答：

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

        auto dfs = [&](this auto&& dfs, vector<vector<bool>>& visited, int pre, int i, int j) {
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || pre > heights[i][j]) {
                return;
            }

            visited[i][j] = true;
            dfs(visited, heights[i][j], i + 1, j + 0);
            dfs(visited, heights[i][j], i - 1, j + 0);
            dfs(visited, heights[i][j], i + 0, j - 1);
            dfs(visited, heights[i][j], i + 0, j + 1);
        };

        for (int i = 0; i < m; ++i) {
            dfs(pacific, INT_MIN, i, 0);
            dfs(atlantic, INT_MIN, i, n - 1);
        }
        for (int i = 0; i < n; ++i) {
            dfs(pacific, INT_MIN, 0, i);
            dfs(atlantic, INT_MIN, m - 1, i);
        }

        vector<vector<int>> ans;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    ans.push_back({ i, j });
                }
            }
        }

        return ans;
    }
};