1
class Solution {
2
 public:
3
  void dfs(vector<vector<int>> &heights, vector<vector<bool>> &v, int i, int j) {
4
    int m = heights.size();
5
    int n = heights[0].size();
6
    v[i][j] = true;
7
    if (i - 1 >= 0 && v[i - 1][j] != true && heights[i - 1][j] >= heights[i][j]) {
8
      dfs(heights, v, i - 1, j);
9
    }
10
    if (i + 1 < m && v[i + 1][j] != true && heights[i + 1][j] >= heights[i][j]) {
11
      dfs(heights, v, i + 1, j);
12
    }
13
    if (j - 1 >= 0 && v[i][j - 1] != true && heights[i][j - 1] >= heights[i][j]) {
14
      dfs(heights, v, i, j - 1);
15
    }
16
    if (j + 1 < n && v[i][j + 1] != true && heights[i][j + 1] >= heights[i][j]) {
17
      dfs(heights, v, i, j + 1);
18
    }
19
  }
20
  vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) {
21
    int m = heights.size();
22
    vector<vector<int>> ans;
23
    if (m == 0) {
24
      return ans;
25
    }
26
    int n = heights[0].size();
27
    if (n == 0) {
28
      return ans;
29
    }
30
    vector<vector<bool>> pa(m, vector<bool>(n));
31
    vector<vector<bool>> at(m, vector<bool>(n));
32
    for (int i = 0; i < m; i++) {
33
      dfs(heights, pa, i, 0);
34
      dfs(heights, at, i, n - 1);
35
    }
36
    for (int j = 0; j < n; j++) {
37
      dfs(heights, pa, 0, j);
38
      dfs(heights, at, m - 1, j);
39
    }
40
    for (int i = 0; i < m; i++) {
41
      vector<int> p;
42
      for (int j = 0; j < n; j++) {
43
        if (pa[i][j] && at[i][j]) {
44
          p.push_back(i);
45
          p.push_back(j);
46
          ans.push_back(p);
47
          p.clear();
48
        }
49
      }
50
    }
51
    return ans;
52
  }
53
};