static int[][] dirs={{0,-1},{0,1},{1,0},{-1,0}};//方向
static int m;
static int n;
static int[][] heights;
List<List<Integer>> pacificAtlantic(int[][] h) {
heights=h;
m=heights.length;
n=heights[0].length;
//考虑从边界逆流搜索能到达的格子
int[][] to1=new int[m][n];//大西洋
int[][] to2=new int[m][n];//太平洋
List<List<Integer>> ans=new ArrayList<>();
//从四条边界搜索
for(int i=0;i<m;i++){
dfs(to1,i,0);
dfs(to2,i,n-1);
}
for(int i=0;i<n;i++){
dfs(to1,0,i);
dfs(to2,m-1,i);
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(to1[i][j]==1&&to2[i][j]==1){
List<Integer> tmp=new ArrayList<>();
tmp.add(i);
tmp.add(j);
ans.add(tmp);
}
}
}
return ans;
}
void dfs(int[][] to,int r,int c){
if(to[r][c]==0)
to[r][c]++;
for(int[] dir:dirs){
//判断下一个格子是否合法,或者已经到达
if(r+dir[0]>=0&&r+dir[0]<m&&c+dir[1]>=0&&c+dir[1]<n
&& heights[r+dir[0]][c+dir[1]]>=heights[r][c]
&& to[r+dir[0]][c+dir[1]]==0)
dfs(to,r+dir[0],c+dir[1]);
}
}
|
