leetcode417. Pacific Atlantic Water Flow

题目要求

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:
The order of returned grid coordinates does not matter.
Both m and n are less than 150.
Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

假设左上角的所有周围面积为太平洋，右下角的所有面积为大西洋。现在使用数组来表示一大片水域，其中数组的每一个位置上的元素代表某一个小水域的高度。假定水只能从高出流向低处，要求找出所有既可以流向太平洋也可以流向大西洋的水域。

思路和代码

首先需要理解题意，题目中强调了水流可以涌向上下左右四个方向，即水流并非只能一直往左流或是一直往上流才能达到太平洋，它可以绕着圈子转，如下面的例子所示：

{1,2,3},
{8,9,4},
{7,6,5}

高度为6的水域的水可以由 6->5->4 并最终汇入太平洋

这道题目直观上来看是需要以数组中的任意一个位置为起点，分别寻找一条数字由大到小并最终到达左上侧或是右下侧的路径。但是反过来来看，任意一个可以到达大西洋的水流必然会抵达数组左边和上边的任意一点。因此，我们可以以数组的边缘作为起点，寻找所有数字由小到大的路径，该路径上的所有点必然可以到达该边所在的洋流。

这里可以采用深度优先搜索或是广度优先搜索的方式遍历所有的可达水域。停止延伸的条件就是遇到已经访问过的水域或者该水域的高度低于前置水域高度。

代码如下：

public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> result = new ArrayList<>();
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return result;
        int rows = matrix.length;
        int columns = matrix[0].length;
        //能够流入太平洋
        boolean[][] canReachPacific = new boolean[matrix.length][matrix[0].length];
        //能够流入大西洋
        boolean[][] canReachAtlantic = new boolean[matrix.length][matrix[0].length];
        for(int i = 0 ; i<rows ; i++) {
            //以左侧边为起点寻找可以流入太平洋的所有节点
            dfs(matrix, canReachPacific, i, 0);
            //以右侧边为起点寻找可以流入大西洋的所有节点
            dfs(matrix, canReachAtlantic, i, matrix[0].length-1);
        }
        
        for(int i = 0 ; i<columns ; i++) {
            //以上侧边为起点寻找可以流入太平的所有节点
            dfs(matrix, canReachPacific, 0, i);
            //以下侧边为起点寻找可以流入大西洋的所有节点
            dfs(matrix, canReachAtlantic, matrix.length-1,  i);
        }
        
        for(int i = 0 ; i<rows ; i++) {
            for(int j = 0 ; j<columns ; j++) {
                //将即可以流入太平洋也可以流入大西洋的水域加入结果集
                if(canReachPacific[i][j] && canReachAtlantic[i][j]) {
                    result.add(new int[]{
                            i, j
                    });
                }
            }
        }
        return result;
    }