1
class Solution {
2
  public List<List<Integer>> pacificAtlantic(int[][] heights) {
3
    if (heights == null) return null;
4
    if (heights.length == 0) return null;
5
    if (heights[0].length == 0) return null;
6

7
    /** */
8
    boolean[][] po = new boolean[heights.length][heights[0].length];
9
    boolean[][] ao = new boolean[heights.length][heights[0].length];
10

11
    for (int i = 0; i < heights[0].length; i++) {
12
      dfs(heights, i, 0, 0, po); // top
13
      dfs(heights, i, heights.length - 1, 0, ao); // bottom
14
    }
15

16
    for (int i = 0; i < heights.length; i++) {
17
      dfs(heights, 0, i, 0, po); // left
18
      dfs(heights, heights[0].length - 1, i, 0, ao); // right
19
    }
20

21
    List<List<Integer>> ans = new ArrayList<>();
22
    for (int i = 0; i < heights.length; i++) {
23
      for (int j = 0; j < heights[i].length; j++) {
24
        if (ao[i][j] && po[i][j]) {
25
          ArrayList<Integer> ar = new ArrayList<>();
26
          ar.add(i);
27
          ar.add(j);
28
          ans.add(ar);
29
        }
30
      }
31
    }
32

33
    return ans;
34
  }
35

36
  private void dfs(int[][] heights, int x, int y, int h, boolean[][] v) {
37
    if (x < 0 || y < 0 || x >= heights[0].length || y >= heights.length) return;
38
    if (v[y][x] || heights[y][x] < h) return;
39
    v[y][x] = true;
40
    /** left */
41
    dfs(heights, x - 1, y, heights[y][x], v);
42

43
    /** right */
44
    dfs(heights, x + 1, y, heights[y][x], v);
45

46
    /** up */
47
    dfs(heights, x, y - 1, heights[y][x], v);
48

49
    /** down */
50
    dfs(heights, x, y + 1, heights[y][x], v);
51
  }
52
}