Accessible Pacific and Atlantic Regions

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).

Title Description:

   the left side and the upper side are the Pacific Ocean, the right side and the lower side are the Atlantic Ocean, the internal figures represent the altitude, the water in the high altitude area can flow to the low place, and the solution water can flow to all positions in the Pacific Ocean and the Atlantic Ocean.

Thought analysis:

   starting from the boundary, the left boundary and upper boundary elements can flow into the Pacific Ocean, and the right boundary and lower boundary elements can flow into the Atlantic Ocean. We traverse the boundary elements, and then carry out the depth first traversal on the boundary elements. If the element value encountered in the depth first traversal is greater than the boundary element, then we prove that it can flow into the corresponding ocean, and then continue to The element is traversed in depth first until it encounters a smaller element and stops traversing. Finally, we look at the elements in the array. If we can reach both the Pacific Ocean and the Atlantic Ocean, then this element is the result that meets the requirements and returns its coordinates.

Code:

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]; //Record whether a node can reach the Pacific Ocean
    boolean[][]canReacha=new boolean[matrix.length][matrix[0].length];//Record whether a node can reach the Atlantic Ocean
    for(int i=0;i<matrix.length;i++){
        dfs(matrix,i,0,canReachp);//Start from the left border to see if the elements can reach the Pacific Ocean.
        dfs(matrix,i,matrix[0].length-1,canReacha); //Start from the right border and look for elements that can reach the Atlantic Ocean.
    }
    for(int j=0;j<matrix[0].length;j++){
        dfs(matrix,0,j,canReachp);//Starting from the upper boundary, we can search deeply to see if the elements can reach the Pacific Ocean.
        dfs(matrix,matrix.length-1,j,canReacha); //Start from the lower boundary to see if the elements can reach the Atlantic Ocean.
    }
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if(canReachp[i][j]&&canReacha[i][j]){//It can reach both the Atlantic and the Pacific
                res.add(new int[]{i,j});
            }
        }
    }
    return res;
}
public void dfs(int[][]matrix,int i,int j,boolean[][]canReach){
    if(canReach[i][j]) //Avoid duplication
        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);
  }