Untitled
unknown
plain_text
a year ago
1.3 kB
4
Indexable
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; } };
Editor is loading...
Leave a Comment