aboutsummaryrefslogtreecommitdiff
path: root/pacific_atlantic_water_flow.cpp
blob: 1bfc6736b05e6deedb97cf3907780b4d1de96d8f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "leetcode.h"

class Solution {
public:
  vvd(int) pacificAtlantic(vvd(int) & heights) {
    n = heights.size();
    m = heights[0].size();
    vvd(bool) flag1(n, vector<bool>(m)), flag2(n, vector<bool>(m));
    vvd(int) ans;
    for (int i = 0; i < n; i++)
      dfs(heights, flag1, i, 0);
    for (int i = 1; i < m; i++)
      dfs(heights, flag1, 0, i);
    for (int i = 0; i < n; i++)
      dfs(heights, flag2, i, m - 1);
    for (int i = 0; i < m - 1; i++)
      dfs(heights, flag2, n - 1, i);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (flag1[i][j] && flag2[i][j])
          ans.push_back({i, j});
    return ans;
  }

private:
  int n, m;
  void dfs(vvd(int) & grid, vvd(bool) & flag, int x, int y) {
    flag[x][y] = true;
    if (x - 1 >= 0 && !flag[x - 1][y] && grid[x - 1][y] >= grid[x][y])
      dfs(grid, flag, x - 1, y);
    if (x + 1 < n && !flag[x + 1][y] && grid[x + 1][y] >= grid[x][y])
      dfs(grid, flag, x + 1, y);
    if (y - 1 >= 0 && !flag[x][y - 1] && grid[x][y - 1] >= grid[x][y])
      dfs(grid, flag, x, y - 1);
    if (y + 1 < m && !flag[x][y + 1] && grid[x][y + 1] >= grid[x][y])
      dfs(grid, flag, x, y + 1);
  }
};