417. Pacific Atlantic Water Flow

解題思路

反向思考，從海到陸是否可以。

用 dfs 解兩次。

程式碼

class Solution {
public:

    void dfs(int x, int y, vector<vector<int>>& heights, vector<vector<bool>>& isVisited, int prevH)
    {
        if(x < 0 || y < 0 || x >= heights.size() || y >= heights[0].size() 
        || isVisited[x][y] || heights[x][y] < prevH)
            return;
        isVisited[x][y] = true;
        dfs(x - 1, y, heights, isVisited, heights[x][y]);
        dfs(x + 1, y, heights, isVisited, heights[x][y]);
        dfs(x, y - 1, heights, isVisited, heights[x][y]);
        dfs(x, y + 1, heights, isVisited, heights[x][y]);
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<bool>> pac(heights.size(), vector<bool>(heights[0].size(), false));
        vector<vector<bool>> alt(heights.size(), vector<bool>(heights[0].size(), false));

        for(int i=0; i<heights.size(); i++)
        {
            dfs(i, 0, heights, pac, heights[i][0]);
            dfs(i, heights[0].size() - 1, heights, alt, heights[i][heights[0].size() - 1]);
        }
        for(int i=0; i<heights[0].size(); i++)
        {
            dfs(0, i, heights, pac, heights[0][i]);
            dfs(heights.size() - 1, i, heights, alt, heights[heights.size()- 1][i]);
        }

        vector<vector<int>> ans;
        for(int i=0; i<heights.size(); i++)
        {
            for(int j=0; j<heights[0].size(); j++)
            {
                if(pac[i][j] && alt[i][j])
                    ans.push_back({i, j});
            }
        }
        return ans;

    }
};