aboutsummaryrefslogtreecommitdiff
path: root/other/pacific_atlantic_water_flow.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/pacific_atlantic_water_flow.cpp')
-rw-r--r--other/pacific_atlantic_water_flow.cpp38
1 files changed, 38 insertions, 0 deletions
diff --git a/other/pacific_atlantic_water_flow.cpp b/other/pacific_atlantic_water_flow.cpp
new file mode 100644
index 0000000..8876d9f
--- /dev/null
+++ b/other/pacific_atlantic_water_flow.cpp
@@ -0,0 +1,38 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vvd pacificAtlantic(vvd & heights) {
+ n = heights.size();
+ m = heights[0].size();
+ vvd(bool) flag1(n, vector<bool>(m)), flag2(n, vector<bool>(m));
+ vvd 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 & 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);
+ }
+};