题目描述

给定一个 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]] (上图中带括号的单元).

算法1

(DFS枚举) O(mn)

每一个点单独都有路径来通向两大洋。我最开始想的是对于每个点都来搜索是否能到达边缘，结果毫无悬念TLE。
其实这道题和LeetCode130 SurroundedRegions类似，都是换一个方向考虑问题,需要从四个边的点向内搜索。这样反向可以减少很多无用的重复搜索，把所有边缘点当作起点开始遍历搜索，然后标记能到达的点为 true。最后分别标记出 pacific 和 atlantic 能到达的点，那么最终能返回的点就是二者均为 true 的点。

Java 代码

class Solution {

    int m, n = 0;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    List<List<Integer>> res = new ArrayList<>();
    // 能到太平洋的坐标集合,true表示能到
    boolean[][] pacific = null;
    // 能到大西洋的坐标集合,true表示能到
    boolean[][] atlantic = null;

    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null) {
            return res;
        }

        m = matrix.length;
        n = matrix[0].length;
        pacific = new boolean[m][n];
        atlantic = new boolean[m][n];

        // 第一列, 最后一列
        for (int i = 0; i < m; i++) {
            // 西部太平洋，东部大西洋向内陆dfs搜索能到的点
            dfs(matrix, i, 0, Integer.MIN_VALUE, pacific);
            dfs(matrix, i, n - 1, Integer.MIN_VALUE, atlantic);
        }

        // 第一行, 最后一行
        for (int j = 0; j < n; j++) {
            // 北部太平洋，南部大西洋向内陆dfs搜索能到的点
            dfs(matrix, 0, j, Integer.MIN_VALUE, pacific);
            dfs(matrix, m - 1, j, Integer.MIN_VALUE, atlantic);
        }

        // 分别标记出 pacific 和 atlantic 能到达的点，那么最终能返回的点就是二者均为 true 的点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }

        return res;
    }

    /**
     * 从[row, col]向内陆dfs搜索能到的点
     * @param matrix    原始数组
     * @param row       当前横坐标
     * @param col       当前纵坐标
     * @param preH      之前点的高度
     * @param visited   当前到达的大洋的点的坐标
     */
    private void dfs(int[][] matrix, int row, int col, int preH, boolean[][] visited) {
        if (visited[row][col] || matrix[row][col] < preH) {
            return;
        }
        visited[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int x = row + dx[i];
            int y = col + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n) {
                dfs(matrix, x, y, matrix[row][col], visited);
            }
        }
        // 不用回溯
    }
}