LeetCode Pacific Atlantic Water Flow

· 750 words · 2 minute read
2017年7月
LeetCode

417. 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:

  1. The order of returned grid coordinates does not matter.
  2. 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).

方法

一开始看到这道题，果断dfs，即判断该点能不能既通向pa也通向atl,可是懵逼，突然发现不会写了，感觉判断太麻烦。

这道题我感觉是我刷LeetCode medium题目以来遇到的最难的题目，其中涵盖了许多思想：dfs+类似于分治（即通向pa和通向atl分开来做，最后取交集）+如何处理方向。

方法：

分别处理海洋，从海洋边缘开始搜索。哪些节点的高度高于等于自身（既反过来可以流到自己），则标记为true,最后所有标记为true的位置就是可以流到对应的海洋。最后两个海洋中为true的做交集，得解。

本题还有一个让我学习的点就是方向的处理，本文使用了一个二维数组来存方向，并不是之前递归时常用的dfs(i,j),dfs(i+1,j)等等。对于做题，有时候就是要突破自己常有的思维定式！！！

public class Solution {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return new ArrayList();
        }
        List<int[]> list = new ArrayList<int[]>();
        int n = matrix.length;
        int m = matrix[0].length;

        boolean[][] pa = new boolean[n][m];
        boolean[][] al = new boolean[n][m];

        // 这里从所有临海的地方到这回去判断某个节点是否能流到对应的地方
        for(int i = 0; i < n; i++){
            flow(matrix,i,0,pa);
            flow(matrix,i,m-1,al);
        }
        for(int j = 0; j < m; j++){
            flow(matrix,0,j,pa);
            flow(matrix,n-1,j,al);
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(pa[i][j] && al[i][j]){
                    list.add(new int[]{i,j});
                }
            }
        }
        return list;
    }

    int[][] d = new int[][]{{0,-1},{0,1},{1,0},{-1,0}};
    public void flow(int[][] matrix, int i, int j, boolean[][] visited){
        if(visited[i][j] == true){
            return;
        }
        visited[i][j] = true;
        for(int[] dy : d){
            int ni = i + dy[0];
            int nj = j + dy[1];
            //一个节点是只能留到不高于自己高度的节点，但是我们这里是反过来找能从ni,nj留到xy的节点
            if(ni >= 0 && ni < matrix.length && nj >=0 && nj < matrix[0].length && matrix[ni][nj] >= matrix[i][j]){
                flow(matrix,ni,nj,visited);
            }
        }
    }
}
Share