能到达的太平洋和大西洋的区域
417. Pacific Atlantic Water Flow (Medium)
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
题目描述：
左边和上边是太平洋，右边和下边是大西洋，内部的数字代表海拔，海拔高的地方的水能够流到低的地方，求解水能够流到太平洋和大西洋的所有位置。
思路分析：
从边界出发，左边界和上边界元素都可以流进太平洋，右边界和下边界元素都可以流进大西洋，我们遍历边界元素，然后对边界元素进行深度优先遍历，如果在深度优先遍历的过程中遇到的元素值，大于边界元素，那么证明其可以流入对应的海洋，然后继续对该元素进行深度优先遍历，直到遇见的元素都比其小从而停止遍历。最后我们查看数组中的元素，如果既能到达太平洋又能到达大西洋，那么这个元素就是满足要求得结果，返回其坐标。
代码：
public List<int[]>pacificAtlantic(int[][]matrix){
List<int []>res=new ArrayList<>();
if(matrix==null||matrix.length==0)
return res;
boolean[][]canReachp=new boolean[matrix.length][matrix[0].length]; //记录某个节点是否能到太平洋
boolean[][]canReacha=new boolean[matrix.length][matrix[0].length];//记录某个节点是否能到达大西洋
for(int i=0;i<matrix.length;i++){
dfs(matrix,i,0,canReachp);//从左边界开始深搜看是否元素能到达太平洋
dfs(matrix,i,matrix[0].length-1,canReacha); //从右边界开始深搜看是否元素能到达大西洋
}
for(int j=0;j<matrix[0].length;j++){
dfs(matrix,0,j,canReachp);//从上边界开始深搜看元素是否能到达太平洋
dfs(matrix,matrix.length-1,j,canReacha); //从下边界开始深搜看元素是否能到到达大西洋
}
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(canReachp[i][j]&&canReacha[i][j]){//既能到达大西洋又能到达太平洋
res.add(new int[]{i,j});
}
}
}
return res;
}
public void dfs(int[][]matrix,int i,int j,boolean[][]canReach){
if(canReach[i][j]) //避免重复
return;
canReach[i][j]=true;
if(i+1<matrix.length&&matrix[i][j]<=matrix[i+1][j])
dfs(matrix,i+1,j,canReach);
if(i-1>=0&&matrix[i][j]<=matrix[i-1][j])
dfs(matrix,i-1,j,canReach);
if(j+1<matrix[0].length&&matrix[i][j]<=matrix[i][j+1])
dfs(matrix,i,j+1,canReach);
if(j-1>=0&&matrix[i][j]<=matrix[i][j-1])
dfs(matrix,i,j-1,canReach);
}