leetcode

commit 5104fc73718d42f9e5df45373a78fa4b195e8e28
parent ee096760122bbe4f1033801c34c9bef0fdbf040e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 29 Nov 2024 18:25:04 +0100

Daily Problem

Diffstat:
A
Problems/2577.cpp
 | 
39
+++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 40 insertions(+), 0 deletions(-)
diff --git a/Problems/2577.cpp b/Problems/2577.cpp
@@ -0,0 +1,39 @@
+class Solution {
+  public:
+    int minimumTime(vector<vector<int>> &grid) const {
+        const int n = size(grid), m = size(grid[0]);
+
+        static const int offset[] = {-1, 0, 1, 0, -1};
+        const auto is_valid = [&](const int x, const int y) {
+            return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] >= 0;
+        };
+
+        using type_t = tuple<int, int, int>;
+        priority_queue<type_t, vector<type_t>, greater<>> pq;
+
+        if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
+        for (pq.emplace(0, 0, 0); !pq.empty();) {
+            const auto [time, a, b] = pq.top();
+            pq.pop();
+
+            if (a == n - 1 && b == m - 1) return time;
+
+            for (int k = 0; k < 4; k++) {
+                const int x = a + offset[k + 1];
+                const int y = b + offset[k];
+
+                if (!is_valid(x, y)) continue;
+
+                const int req = grid[x][y];
+                if (time + 1 >= req)
+                    pq.emplace(time + 1, x, y);
+                else
+                    pq.emplace(req + !((req - time) % 2), x, y);
+
+                grid[x][y] = -1;
+            }
+        }
+
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -1347,6 +1347,7 @@ reference and a base for solving problems.
 |  2563  |   Medium   | [Count the Number of Fair Pairs](Problems/2563.cpp)                                                |
 |  2568  |   Medium   | [Minimum Impossible OR](Problems/2568.cpp)                                                         |
 |  2571  |   Medium   | [Minimum Operations to Reduce an Integer to 0](Problems/2571.cpp)                                  |
+|  2577  |    Hard    | [Minimum Time to Visit a Cell In a Grid](Problems/2577.cpp)                                        |
 |  2579  |   Medium   | [Count Total Number of Colored Cells](Problems/2579.cpp)                                           |
 |  2582  |    Easy    | [Pass the Pillow](Problems/2582.cpp)                                                               |
 |  2583  |   Medium   | [Kth Largest Sum in a Binary Tree](Problems/2583.cpp)                                              |