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

1.题目：

https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

示例 1：

输入: heights = [[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]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

2.代码：

dfs：

class Solution {
    int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
    boolean[][][] visited;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        int rowSize = heights.length;
        int colSize = heights[0].length;
        visited = new boolean[rowSize][colSize][2];
        // 记录 [row, col] 位置是否可以到某条河，可以为 true，反之为 false；
        // 假设太平洋的标记为 1，大西洋为 0
        for(int i=0;i<rowSize;i++){
           visited[i][0][1]=true;//左-太平洋
           visited[i][colSize-1][0]=true;//右-大西洋
           dfs(heights,i,0,1);
           dfs(heights,i,colSize-1,0);
        }
        for(int j=0;j<colSize;j++){
            visited[0][j][1]=true;//上-太平洋
            visited[rowSize-1][j][0]=true;//下-大西洋
            dfs(heights,0,j,1);
            dfs(heights,rowSize-1,j,0);
        }
        for(int i=0;i<rowSize;i++){
            for(int j=0;j<colSize;j++){
                if(visited[i][j][0] && visited[i][j][1]){
                    // 如果该位置即可以到太平洋又可以到大西洋，就放入答案数组
                    result.add(List.of(i,j));
                }
            }
        }
        return result;
    }
    public void dfs(int[][] heights,int row,int col,int sign){
        for(int i=0;i<move.length;i++){
            int m = row+move[i][0];
            int n = col+move[i][1];
            if(m<0||n<0||m>=heights.length||n>=heights[0].length) continue;// 越界
            // 高度不合适或者已经被访问过了
            if(heights[m][n]<heights[row][col] || visited[m][n][sign]) continue;
            visited[m][n][sign]=true;
            dfs(heights,m,n,sign);
        }
    }
}