[数据结构与算法]417. 太平洋大西洋水流问题

417. 太平洋大西洋水流问题

LeetCode刷题打卡第028天 _{（第1篇） 20210806}

题目链接

思路

1. 联系深度遍历，想到可以运用深度遍历
2. 虽然题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那么在不剪枝的情况下复杂度会很高。
3. 因此我们可以反过来想，从两个大洋开始向上流，这样我们只需要对矩形四条边进行搜索。搜索完成后，只需遍历一遍矩阵，满足条件的位置即为两个大洋向上流都能到达的位置。

代码

class Solution {
public:
     vector<int> direction{-1, 0, 1, 0, -1};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        //运用递归算法，统计可以同时到达太平洋和大西洋的大陆的位置
        //联系深度遍历，想到可以运用深度遍历
        /*
        虽然题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那
        么在不剪枝的情况下复杂度会很高。因此我们可以反过来想，从两个大洋开始向上流，这样我们
        只需要对矩形四条边进行搜索。搜索完成后，只需遍历一遍矩阵，满足条件的位置即为两个大洋
        向上流都能到达的位置。
        */
        if(heights.empty()||heights[0].empty())
            return {};
        int m=heights.size();  
        int n=heights[0].size();  
        vector<vector<bool> > visited_p(m,vector<bool>(n,false));  //用来判断太平洋能够到达的地方
        vector<vector<bool> > visited_a(m,vector<bool>(n,false));
        //用来判断大西洋能到达的地方
        vector<vector<int> > ans;  //返回的答案值，注意返回类型形式

        //需要进行两次遍历，分别判断出太平洋和大西洋到达的地方

        for(int i=0;i<m;i++){
            dfs(heights,visited_p,i,0);
            dfs(heights,visited_a,i,n-1);
        }
        for(int j=0;j<n;j++){
            dfs(heights,visited_p,0,j);
            dfs(heights,visited_a,m-1,j);
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(visited_p[i][j] && visited_a[i][j])
                    ans.push_back(vector<int>{i,j});
            }
        }
        return ans;
    }
// 辅函数
void dfs(vector<vector<int> >&heights,vector<vector<bool> >&visited,int m,int n){
        if(visited[m][n]) return;
        visited[m][n]=true;
        int x,y;
        for (int i = 0; i < 4; i++) {
            x = m + direction[i];
            y = n + direction[i+1];
            if (x >= 0 && x < heights.size() && y >= 0 && y < heights[0].size() && heights[m][n] <= heights[x][y]) {
                dfs(heights, visited, x, y);
            }
        }
    }
};