讨论/《深度优先搜索》 - 练习:太平洋大西洋水流问题/
《深度优先搜索》 - 练习:太平洋大西洋水流问题
共 1 个回复
class Solution {
public:

    bool pacific(vector<vector<int>>& matrix , int i, int j, int pre){
        int m=matrix.size();
        int n=matrix[0].size();
        if(i>=m || j>=n || matrix[i][j]==-1 || matrix[i][j]>pre ) //move bottom or right
            return false;
        if(i<=0 || j<=0)  //move  top and left
            return true;
        int temp=matrix[i][j];
        matrix[i][j]=-1;
        bool result=pacific(matrix, i-1,j,temp)
                    ||pacific(matrix, i+1,j,temp)
                    ||pacific(matrix, i,j-1,temp)
                    ||pacific(matrix, i,j+1,temp);
        matrix[i][j]=temp;
        return result;
    }


    bool atlantic(vector<vector<int>>& matrix , int i, int j, int pre){
        int m=matrix.size();
        int n=matrix[0].size();
        if(i<0 || j<0 || matrix[i][j]==-1 || matrix[i][j]>pre ) //move top or left
            return false;
        if(i>=m-1 || j>=n-1)  //move bottom or right
            return true;
        int temp=matrix[i][j];
        matrix[i][j]=-1;
        bool result=atlantic(matrix, i-1,j,temp)
                    ||atlantic(matrix, i+1,j,temp)
                    ||atlantic(matrix, i,j-1,temp)
                    ||atlantic(matrix, i,j+1,temp);
        matrix[i][j]=temp;
        return result;
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        vector<vector<int>> results;
        int m=matrix.size();
        if(m==0)
            return results;  
        int n=matrix[0].size();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(pacific(matrix,i, j, INT_MAX) && atlantic(matrix, i, j, INT_MAX)){
                    results.push_back({i,j});
                }
            }
        }
        return results;
    }
};