leetcode

commit ee096760122bbe4f1033801c34c9bef0fdbf040e
parent 2847b1ee0ab72094a43ca4a1803d2d24676f28d7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 28 Nov 2024 15:14:20 +0100

Daily Problem

Diffstat:
A
Problems/2290.cpp
 | 
34
++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 35 insertions(+), 0 deletions(-)
diff --git a/Problems/2290.cpp b/Problems/2290.cpp
@@ -0,0 +1,34 @@
+class Solution {
+  public:
+    int minimumObstacles(vector<vector<int>> &grid) const {
+        const int n = size(grid), m = size(grid[0]);
+
+        vector<vector<int>> d(n, vector(m, INT_MAX / 2));
+        deque<pair<int, int>> dq = {{0, 0}};
+
+        static const int offset[] = {-1, 0, 1, 0, -1};
+        const auto valid = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; };
+
+        for (d[0][0] = 0; !dq.empty();) {
+            const auto [a, b] = dq.front();
+            dq.pop_front();
+
+            for (int k = 0; k < 4; k++) {
+                const int x = a + offset[k + 1];
+                const int y = b + offset[k];
+
+                if (!valid(x, y) || d[x][y] != INT_MAX / 2) continue;
+                if (d[a][b] + grid[x][y] >= d[x][y]) continue;
+
+                d[x][y] = d[a][b] + grid[x][y];
+
+                if (grid[x][y] == 1)
+                    dq.emplace_back(x, y);
+                else
+                    dq.emplace_front(x, y);
+            }
+        }
+
+        return d[n - 1][m - 1];
+    }
+};
diff --git a/README.md b/README.md
@@ -1251,6 +1251,7 @@ reference and a base for solving problems.
 |  2279  |   Medium   | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp)                                      |
 |  2284  |   Medium   | [Sender With Largest Word Count](Problems/2284.cpp)                                                |
 |  2285  |   Medium   | [Maximum Total Importance of Roads](Problems/2285.cpp)                                             |
+|  2290  |    Hard    | [Minimum Obstacle Removal to Reach Corner](Problems/2290.cpp)                                      |
 |  2294  |   Medium   | [Partition Array Such That Maximum Difference Is K](Problems/2294.cpp)                             |
 |  2295  |   Medium   | [Replace Elements in an Array](Problems/2295.cpp)                                                  |
 |  2300  |   Medium   | [Successful Pairs of Spells and Potions](Problems/2300.cpp)                                        |