Leetcode--Java--417. 太平洋大西洋水流问题

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

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

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

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

DFS/BFS (多源BFS)+ 反向思维

1. 利用深搜或者广搜，题中要找的是同时流向两块海域的坐标，可以逆向思维，从两块海域的每个边界开始，找能够“水往高处流”的点，求两者之间的交集就是答案
2. 反向思维的好处，如果直接爆搜某个点达到某种海域，判断起来很复杂，因为边界有很多点，反向的话更容易理解
3. 注意两块海域的起始位置
4. 注意BFS的话，有多个源头，要全部入队

DFS：

class Solution {
    int g[][];
    int m, n;
    int dx[] = new int[]{0, 1, 0 ,-1};
    int dy[] = new int[]{1, 0, -1, 0};
    public List> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        g = heights;
        boolean res1[][] = new boolean[m][n];
        boolean res2[][] = new boolean[m][n];
        //水往高处流
        for(int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                //太平洋
                if (i == 0 || j == 0) {
                    if (!res1[i][j]) {
                        res1[i][j] = true;
                        dfs(res1, i, j);
                    }
                }
                //大西洋
                if (i == m - 1 || j == n - 1) {
                    if (!res2[i][j]) {
                        res2[i][j] = true;
                        dfs(res2, i, j);
                    }
                }
            }
        }
        //两个的交集就是能流向两个海域的
        List> res = new ArrayList<>();
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (res1[i][j] && res2[i][j]) {
                    List coordinate = new ArrayList<>();
                    coordinate.add(i);
                    coordinate.add(j);
                    res.add(coordinate);
                }
            }
        }
        return res;
    }
    public void dfs(boolean res[][], int x, int y) {
        res[x][y] = true;
        for (int d = 0; d < 4; d ++ ) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || res[nx][ny] || g[nx][ny] < g[x][y]) continue;
            dfs(res, nx, ny);
        }
    }
}

BFS:

class Solution {
    int g[][];
    int m, n;
    int dx[] = new int[]{0, 1, 0, -1};
    int dy[] = new int[]{1, 0, -1, 0};
    public List> pacificAtlantic(int[][] heights) {
        g = heights;
        m = heights.length;
        n = heights[0].length;
        Deque q1 = new LinkedList<>();
        Deque q2 = new LinkedList<>();
        boolean res1[][] = new boolean[m][n];
        boolean res2[][] = new boolean[m][n];
        //多源BFS
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (i == 0 || j == 0) {
                    res1[i][j] = true;
                    q1.offer(new int[]{i, j});
                    bfs(q1, res1);
                }
                if (i == m - 1 || j == n - 1) {
                    res2[i][j] = true;
                    q2.offer(new int[]{i, j});
                    bfs(q2, res2);
                }
            }
        }

        List> ans = new ArrayList<>();
        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (res1[i][j] && res2[i][j]) {
                    List list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
            }
        }
        return ans;

    }
    public void bfs(Deque d, boolean res[][]) {
        while (!d.isEmpty()) {
            int coordinate[] = d.poll();
            int x = coordinate[0], y = coordinate[1];
            for (int i = 0; i < 4; i ++ ) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || res[nx][ny] || g[nx][ny] < g[x][y]) {
                    continue;
                }
                res[nx][ny] = true;
                d.offer(new int[]{nx, ny});
            }
        }
    }
}