|
| 1 | +publicclassSolution{ |
| 2 | + |
| 3 | +publicIList<IList<int>>PacificAtlantic(int[][]heights) |
| 4 | +{ |
| 5 | +List<IList<int>>res=new(); |
| 6 | +intm=heights.Length,n=heights[0].Length; |
| 7 | +bool[,]isPacific=newbool[m,n]; |
| 8 | +bool[,]isAtlantic=newbool[m,n]; |
| 9 | +for(introw=0;row<m;row++) |
| 10 | +{ |
| 11 | +DFSPacificAtlantic(row,0,heights,isPacific,heights[row][0]); |
| 12 | +DFSPacificAtlantic(row,n-1,heights,isAtlantic,heights[row][n-1]); |
| 13 | +} |
| 14 | + |
| 15 | +for(intcol=0;col<n;col++) |
| 16 | +{ |
| 17 | +DFSPacificAtlantic(0,col,heights,isPacific,heights[0][col]); |
| 18 | +DFSPacificAtlantic(m-1,col,heights,isAtlantic,heights[m-1][col]); |
| 19 | +} |
| 20 | +for(inti=0;i<m;i++) |
| 21 | +{ |
| 22 | +for(intj=0;j<n;j++) |
| 23 | +{ |
| 24 | +if(isAtlantic[i,j]&&isPacific[i,j]) |
| 25 | +{ |
| 26 | +res.Add(newList<int>{i,j}); |
| 27 | +} |
| 28 | +} |
| 29 | +} |
| 30 | + |
| 31 | +returnres; |
| 32 | +} |
| 33 | + |
| 34 | +privatevoidDFSPacificAtlantic(introw,intcol,int[][]heights,bool[,]visits,intprev) |
| 35 | +{ |
| 36 | +intm=heights.Length,n=heights[0].Length; |
| 37 | +if(row<0||row>=m||col<0||col>=n||visits[row,col]||heights[row][col]<prev) |
| 38 | +return; |
| 39 | +visits[row,col]=true; |
| 40 | +DFSPacificAtlantic(row,col+1,heights,visits,heights[row][col]); |
| 41 | +DFSPacificAtlantic(row,col-1,heights,visits,heights[row][col]); |
| 42 | +DFSPacificAtlantic(row+1,col,heights,visits,heights[row][col]); |
| 43 | +DFSPacificAtlantic(row-1,col,heights,visits,heights[row][col]); |
| 44 | +} |
| 45 | +} |