太平洋大西洋水流

问题陈述

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定下面的 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]] (上图中带括号的单元).


思路分析

思路是从海洋开始逆流 如果可以逆流到 就标记为1 然后检查两个海洋都可以逆流到的区域。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution{
    public List<List<Integer>> pacificAndAtlantic(int[][] matrix){
        if(matrix==null||matrix.length==0){
            return new ArrayList<>();
        }
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] pacific=new int[m][n];
        int[][] atlantic=new int[m][n];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    dfs(matrix,pacific,i,j,matrix[i][j]);
                }
                if(i==m-1||j==n-1){
                    dfs(matrix,atlantic,i,j,matrix[i][j]);
                }
            }
        }
        
        List<List<Integer>> res=new ArrayList<>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(pacific[i][j]==1&&atlantic[i][j]==1){
                    res.add(Arrays.asList(i,j));
                }
            }
        }
        return res;
    }
    public void dfs(int[][] matrix,int[][] ocean,int i,int j,int pre){
        if(i<0 || i>=matrix.length || j<0 || j>=matrix[0].length || ocean[i][j]==1 || matrix[i][j]<pre){
            return;
        }
        ocean[i][j]=1;
        dfs(matrix, ocean, i - 1, j, matrix[i][j]);
        dfs(matrix, ocean, i + 1, j, matrix[i][j]);
        dfs(matrix, ocean, i, j - 1, matrix[i][j]);
        dfs(matrix, ocean, i, j + 1, matrix[i][j]);
    }
}