leetcode

commit 97285c339642cfaa840f23b1f9e9b317ca56f9b8
parent 378592e743fe6936190a75b51a8da1d3df7d087a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 11 Aug 2024 11:58:55 +0200

Daily Problem

Diffstat:
A
Problems/1568.cpp
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 56 insertions(+), 0 deletions(-)
diff --git a/Problems/1568.cpp b/Problems/1568.cpp
@@ -0,0 +1,55 @@
+class Solution {
+    bool isDisconected(const vector<vector<int>> &grid) const {
+        const int n = size(grid), m = size(grid[0]);
+        bool seen = false;
+
+        static int visit[31][31];
+        memset(visit, 0x00, sizeof(visit));
+
+        queue<pair<int, int>> q;
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++) {
+                if (!grid[i][j] || visit[i][j]) continue;
+                if (seen) return true;
+                seen = true;
+
+                q.emplace(i, j);
+                while (!q.empty()) {
+                    const auto [a, b] = q.front();
+                    q.pop();
+
+                    static const int dir[] = {-1, 0, 1, 0, -1};
+                    for (int k = 0; k < 4; k++) {
+                        const int x = a + dir[k];
+                        const int y = b + dir[k + 1];
+
+                        if (x < 0 || y < 0 || x >= n || y >= m) continue;
+                        if (!grid[x][y] || visit[x][y]) continue;
+                        q.emplace(x, y);
+                        visit[x][y] = 1;
+                    }
+                }
+            }
+        }
+
+        return !seen;
+    }
+
+  public:
+    int minDays(vector<vector<int>> &grid) const {
+        const int n = size(grid), m = size(grid[0]);
+
+        if (isDisconected(grid)) return 0;
+        for (int i = 0; i < n; i++) {
+            for (int j = 0; j < m; j++) {
+                if (!grid[i][j]) continue;
+
+                grid[i][j] = 0;
+                if (isDisconected(grid)) return 1;
+                grid[i][j] = 1;
+            }
+        }
+
+        return 2;
+    }
+};
diff --git a/README.md b/README.md
@@ -885,6 +885,7 @@ for solving problems.
 |  1558  |   Medium   | [Minimum Numbers of Function Calls to Make Target Array](Problems/1558.cpp)                        |
 |  1561  |   Medium   | [Maximum Number of Coins You Can Get](Problems/1561.cpp)                                           |
 |  1567  |   Medium   | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp)                              |
+|  1568  |    Hard    | [Minimum Number of Days to Disconnect Island](Problems/1568.cpp)                                   |
 |  1569  |    Hard    | [Number of Ways to Reorder Array to Get Same BST](Problems/1569.cpp)                               |
 |  1572  |    Easy    | [Matrix Diagonal Sum](Problems/1572.cpp)                                                           |
 |  1575  |   Medium   | [Count All Possible Routes](Problems/1575.cpp)                                                     |