commit b2bae2ea3099a571005e6c8f79bea05941a27e88
parent 475eb9b9e6ed1c3561cd8ab9f7db7974ccd395a2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 13 Feb 2023 13:09:01 +0100
LeetCode 75 II: Day 10
Diffstat:
2 files changed, 56 insertions(+), 0 deletions(-)
diff --git a/Problems/0417.cpp b/Problems/0417.cpp
@@ -0,0 +1,54 @@
+class Solution {
+ typedef vector<vector<int>> Matrix;
+ typedef vector<vector<bool>> Marked;
+ typedef queue<pair<int, int>> Queue;
+ const vector<pair<int, int>> offsets = {
+ { 0, 1},
+ { 0, -1},
+ { 1, 0},
+ {-1, 0}
+ };
+
+ int n, m;
+ int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+ void dfs(Matrix &mat, Marked &mark, int x, int y) {
+ if (mark[x][y]) return;
+ Queue q;
+
+ q.push({x, y}), mark[x][y] = true;
+ while (!q.empty()) {
+ auto [a, b] = q.front();
+ q.pop();
+ for (auto [oa, ob] : offsets) {
+ int x = a + oa, y = b + ob;
+ if (!valid(x, y) || mark[x][y] || mat[x][y] < mat[a][b]) continue;
+ mark[x][y] = true;
+ q.push({x, y});
+ }
+ }
+ }
+
+public:
+ vector<vector<int>> pacificAtlantic(Matrix &heights) {
+ n = heights.size(), m = heights[0].size();
+ Marked pac(n, vector<bool>(m, false)), atl(n, vector<bool>(m, false));
+
+ for (int i = 0; i < n; i++) {
+ dfs(heights, pac, i, 0);
+ dfs(heights, atl, i, m - 1);
+ }
+
+ for (int i = 0; i < m; i++) {
+ dfs(heights, pac, 0, i);
+ dfs(heights, atl, n - 1, i);
+ }
+
+ vector<vector<int>> res;
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < m; j++)
+ if (pac[i][j] && atl[i][j]) res.push_back({i, j});
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -210,6 +210,7 @@ for solving problems.
| 0413 | Medium | [Arithmetic Slices](Problems/0413.cpp) |
| 0414 | Easy | [Third Maximum Number](Problems/0414.cpp) |
| 0415 | Easy | [Add Strings](Problems/0415.cpp) |
+| 0417 | Medium | [Pacific Atlantic Water Flow](Problems/0417.cpp) |
| 0424 | Medium | [Longest Repeating Character Replacement](Problems/0424.cpp) |
| 0429 | Medium | [N-ary Tree Level Order Traversal](Problems/0429.cpp) |
| 0430 | Medium | [Flatten a Multilevel Doubly Linked list](Problems/0430.cpp) |
@@ -431,3 +432,4 @@ for solving problems.
| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
+
