LeetCode 417. 太平洋大西洋水流问题 JAVA dfs

小咪咪 2022-12-14 00:34 92阅读 0赞

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。  
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。  
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：
    
    输出坐标的顺序不重要
    m 和 n 都小于150
     
    
    示例：
    
     
    
    给定下面的 5x5 矩阵:
    
      太平洋 ~   ~   ~   ~   ~ 
           ~  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  *
              *   *   *   *   * 大西洋
    
    返回:
    
    [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、利用深度搜索算法，注意要先判断边界条件及该点是否已经查看，避免死循环  
2、从边界往四周搜索，即如果周围的水流比边界水流高，那么该点可以到达边界。  
3、利用两个boolean类型数组分别代表太平洋和大西洋，搜索那些点可以分别达到大西洋和太平洋  
4、最终取两个数组并集即答案

class Solution {
        
        boolean Atlantic[][];
        boolean Pacific[][];
        public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        
            List<List<Integer>> res=new ArrayList<>();
            int row=matrix.length;
            if(row==0) return res;
            int col=matrix[0].length;
            Atlantic=new boolean[row][col]; 
            Pacific=new boolean[row][col];
            for(int i=0;i<row;i++)
            {
        
                dfs(matrix, Atlantic,i,col-1);
                dfs(matrix,Pacific,i,0);
            }    
            for(int i=0;i<col;i++)
            {
        
                dfs(matrix,Atlantic,row-1,i);
                dfs(matrix,Pacific,0,i);
            }
            for(int i=0;i<matrix.length;i++)
            {
        
                for(int j=0;j<matrix[i].length;j++)
                {
        
                    if(Atlantic[i][j]&&Pacific[i][j])
                    {
            
                        List<Integer> tmp=new ArrayList<Integer>();
                        tmp.add(i);
                        tmp.add(j);
                        res.add(tmp);
                    }
                }
            }
            return res;
        }
        public void dfs(int matrix[][],boolean visit[][],int row,int col)
        {
        
            if(row<0||row>=matrix.length||col<0||col>=matrix[row].length||visit[row][col])
                return;
            visit[row][col]=true;
            if(row-1>=0&&matrix[row][col]<=matrix[row-1][col])
                dfs(matrix,visit,row-1,col);
            if(row+1<matrix.length&&matrix[row][col]<=matrix[row+1][col])
                dfs(matrix,visit,row+1,col);
            if(col-1>=0&&matrix[row][col]<=matrix[row][col-1])
                dfs(matrix,visit,row,col-1);
            if(col+1<matrix[row].length&&matrix[row][col]<=matrix[row][col+1])
                dfs(matrix,visit,row,col+1);
        }
    }