leetcode

commit 4eba76cf87b984de24105cd5516587543be95faf
parent f09f44fa95e8eebd4941c50c9f242f4f33f3a164
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 15 May 2024 16:32:18 +0200

Daily Problem

Diffstat:
A
Problems/2812.cpp
 | 
63
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 64 insertions(+), 0 deletions(-)
diff --git a/Problems/2812.cpp b/Problems/2812.cpp
@@ -0,0 +1,63 @@
+class Solution {
+  public:
+    int maximumSafenessFactor(vector<vector<int>> &grid) {
+        static int offset[] = {-1, 0, 1, 0, -1};
+        const int n = size(grid);
+
+        using qtype_t = tuple<int, int>;
+        queue<qtype_t> q;
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < n; j++) {
+                if (grid[i][j] != 1) continue;
+                q.emplace(i, j);
+            }
+        }
+
+        for (int lvl = 2; !q.empty(); lvl++) {
+            for (int k = q.size(); k > 0; k--) {
+                const auto [a, b] = q.front();
+                q.pop();
+
+                for (int k = 0; k < 4; k++) {
+                    const int x = a + offset[k + 1];
+                    const int y = b + offset[k];
+
+                    if (x < 0 || x >= n || y < 0 || y >= n) continue;
+                    if (grid[x][y]) continue;
+
+                    grid[x][y] = lvl;
+                    q.emplace(x, y);
+                }
+            }
+        }
+
+        using pqtype_t = tuple<int, int, int>;
+        priority_queue<pqtype_t> pq;
+
+        int res = grid[0][0];
+
+        pq.emplace(grid[0][0], 0, 0);
+        grid[0][0] = -grid[0][0];
+        while (!pq.empty()) {
+            const auto [v, a, b] = pq.top();
+            pq.pop();
+
+            res = min(res, -grid[a][b]);
+            if (a == n - 1 && b == n - 1) return res - 1;
+
+            for (int k = 0; k < 4; k++) {
+                const int x = a + offset[k + 1];
+                const int y = b + offset[k];
+
+                if (x < 0 || x >= n || y < 0 || y >= n) continue;
+                if (grid[x][y] < 0) continue;
+
+                pq.emplace(grid[x][y], x, y);
+                grid[x][y] = -grid[x][y];
+            }
+        }
+
+        return 0;
+    }
+};
diff --git a/README.md b/README.md
@@ -1194,6 +1194,7 @@ for solving problems.
 |  2785  |   Medium   | [Sort Vowels in a String](Problems/2785.cpp)                                                       |
 |  2799  |   Medium   | [Count Complete Subarrays in an Array](Problems/2799.cpp)                                          |
 |  2807  |   Medium   | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp)                                |
+|  2812  |   Medium   | [Find the Safest Path in a Grid](Problems/2812.cpp)                                                |
 |  2816  |   Medium   | [Double a Number Represented as a Linked List](Problems/2816.cpp)                                  |
 |  2840  |   Medium   | [Check if Strings Can be Made Equal With Operations II](Problems/2840.cpp)                         |
 |  2849  |   Medium   | [Determine if a Cell Is Reachable at a Given Time](Problems/2849.cpp)                              |