leetcode

commit 2d501e2544eeca0f90d63eb6cb1afd4dfeb28b84
parent 1b9cdc1a4c8e9064db9f94025e15af2d2d669482
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 21 May 2023 08:46:35 +0200

Daily Problem

Diffstat:
A
Problems/0934.cpp
 | 
58
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 59 insertions(+), 0 deletions(-)
diff --git a/Problems/0934.cpp b/Problems/0934.cpp
@@ -0,0 +1,58 @@
+class Solution {
+  static const constexpr int offs_x[] = {1, 0, -1, 0};
+  static const constexpr int offs_y[] = {0, 1, 0, -1};
+
+  int n;
+
+  bool valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < n; }
+
+public:
+  int shortestBridge(vector<vector<int>> &grid) {
+    queue<pair<int, int>> dq1, dq2;
+    n = grid.size();
+
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < n; j++) {
+        if (!grid[i][j]) continue;
+        dq1.push({i, j});
+        grid[i][j] = 2;
+        goto parse;
+      }
+    }
+
+    return -1;
+
+  parse:
+    while (!dq1.empty()) {
+      auto [i, j] = dq1.front();
+      dq1.pop();
+      for (int k = 0; k < 4; k++) {
+        int a = i + offs_x[k], b = j + offs_y[k];
+        if (!valid(a, b)) continue;
+        if (grid[a][b] == 1)
+          dq1.push({a, b});
+        else if (grid[a][b] == 0)
+          dq2.push({a, b});
+        grid[a][b] = 2;
+      }
+    }
+
+    for (int lvl = 1; !dq2.empty(); lvl++) {
+      for (int k = dq2.size(); k > 0; k--) {
+        auto [i, j] = dq2.front();
+        dq2.pop();
+        for (int k = 0; k < 4; k++) {
+          int a = i + offs_x[k], b = j + offs_y[k];
+          if (!valid(a, b)) continue;
+          if (grid[a][b] == 1)
+            return lvl;
+          else if (grid[a][b] == 0)
+            dq2.push({a, b});
+          grid[a][b] = 2;
+        }
+      }
+    }
+
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -367,6 +367,7 @@ for solving problems.
 |  0926  |   Medium   | [Flip String to Monotone Increasing](Problems/0926.cpp)                                          |
 |  0931  |   Medium   | [Minimum Falling Path Sum](Problems/0931.cpp)                                                    |
 |  0933  |    Easy    | [Number of Recent Calls](Problems/0933.cpp)                                                      |
+|  0934  |   Medium   | [Shortest Bridge](Problems/0934.cpp)                                                             |
 |  0938  |    Easy    | [Range Sum of BST](Problems/0938.cpp)                                                            |
 |  0941  |    Easy    | [Valid Mountain Array](Problems/0941.cpp)                                                        |
 |  0944  |    Easy    | [Delete Columns to Make Sorted](Problems/0944.cpp)                                               |