leetcode

commit a81939f28326b175efee5134855171369447d4d6
parent 807ebd3ef2467af2663643631acbf9cb7c825a9d
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 25 Dec 2024 13:35:50 +0100

1 Random Problem

Diffstat:
A
Problems/0778.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/0778.cpp b/Problems/0778.cpp
@@ -0,0 +1,28 @@
+class Solution {
+  public:
+    int swimInWater(vector<vector<int>> &grid) const {
+        priority_queue<tuple<int, int, int>> pq;
+        const int n = size(grid);
+
+        static const int offset[] = {-1, 0, 1, 0, -1};
+        const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; };
+
+        pq.emplace(-grid[0][0], 0, 0);
+        while (!pq.empty()) {
+            const auto [t, x, y] = pq.top();
+            pq.pop();
+            if (x == n - 1 && y == n - 1) return -t;
+
+            for (int k = 0; k < 4; k++) {
+                const auto a = x + offset[k + 1];
+                const auto b = y + offset[k];
+
+                if (!valid(a, b) || grid[a][b] < 0) continue;
+                pq.emplace(min(t, -grid[a][b]), a, b);
+                grid[a][b] = -1;
+            }
+        }
+
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -577,6 +577,7 @@ reference and a base for solving problems.
 |  0767  |   Medium   | [Reorganize String](Problems/0767.cpp)                                                             |
 |  0769  |   Medium   | [Max Chunks To Make Sorted](Problems/0769.cpp)                                                     |
 |  0773  |    Hard    | [Sliding Puzzle](Problems/0773.cpp)                                                                |
+|  0778  |    Hard    | [Swim in Rising Water](Problems/0778.cpp)                                                          |
 |  0779  |   Medium   | [K-th Symbol in Grammar](Problems/0779.cpp)                                                        |
 |  0781  |   Medium   | [Rabbits in Forest](Problems/0781.cpp)                                                             |
 |  0783  |    Easy    | [Minimum Distance Between BST Nodes](Problems/0783.cpp)                                            |