Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.3 kB
0
Indexable
Never
class Solution {
public:
    void dfs(int x,int y,set<pair<int,int>>&ocean,int &prevHeight,vector<vector<int>>& heights){
        if(ocean.find({x,y})!=ocean.end() || x<0 || y<0 || x>=heights.size() || y>=heights[0].size() || heights[x][y]<prevHeight){
            return;
        }
        ocean.insert({x,y});
        dfs(x+1,y,ocean,heights[x][y],heights);
        dfs(x-1,y,ocean,heights[x][y],heights);
        dfs(x,y+1,ocean,heights[x][y],heights);
        dfs(x,y-1,ocean,heights[x][y],heights);
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>>res;
        set<pair<int,int>> atl,pac;
        int r=heights.size();
        int c=heights[0].size();
        for(int i=0;i<c;i++){
            dfs(0,i,pac,heights[0][i],heights);
            dfs(r-1,i,atl,heights[r-1][i],heights);
        }

        for(int i=0;i<r;i++){
            dfs(i,0,pac,heights[i][0],heights);
            dfs(i,c-1,atl,heights[i][c-1],heights);
        }

        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(pac.find({i,j})!=pac.end() && atl.find({i,j})!=atl.end()){
                    res.push_back({i,j});
                }
            }
        }
        return res;
    }
};
Leave a Comment