leetcode

commit b0a5a3da4551a99057f6694e0981d1109203cf27
parent 115a74cf6f7f8049cc79e16ac9e9b5e57c81b2c9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu,  6 Apr 2023 15:20:55 +0200

Daily Problem

Diffstat:
A
Problems/1254.cpp
 | 
36
++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 37 insertions(+), 0 deletions(-)
diff --git a/Problems/1254.cpp b/Problems/1254.cpp
@@ -0,0 +1,36 @@
+class Solution {
+  int n, m;
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+  void flood_fill(vector<vector<int>> &grid, int x, int y) {
+    grid[x][y] = 1;
+    if (valid(x + 1, y) && !grid[x + 1][y]) flood_fill(grid, x + 1, y);
+    if (valid(x - 1, y) && !grid[x - 1][y]) flood_fill(grid, x - 1, y);
+    if (valid(x, y + 1) && !grid[x][y + 1]) flood_fill(grid, x, y + 1);
+    if (valid(x, y - 1) && !grid[x][y - 1]) flood_fill(grid, x, y - 1);
+  }
+
+public:
+  int closedIsland(vector<vector<int>> &grid) {
+    n = grid.size(), m = grid[0].size();
+    for (int i = 0; i < n; i++) {
+      if (!grid[i][0]) flood_fill(grid, i, 0);
+      if (!grid[i][m - 1]) flood_fill(grid, i, m - 1);
+    }
+    for (int i = 0; i < m; i++) {
+      if (!grid[0][i]) flood_fill(grid, 0, i);
+      if (!grid[n - 1][i]) flood_fill(grid, n - 1, i);
+    }
+
+    int res = 0;
+    for (int i = 1; i < n - 1; i++) {
+      for (int j = 1; j < m - 1; j++) {
+        if (grid[i][j]) continue;
+        flood_fill(grid, i, j);
+        res++;
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -400,6 +400,7 @@ for solving problems.
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |
 |  1209  |   Medium   | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)                                 |
 |  1249  |   Medium   | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp)                                    |
+|  1254  |   Medium   | [Number of Closed Islands](Problems/1254.cpp)                                                 |
 |  1290  |    Easy    | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp)                           |
 |  1302  |   Medium   | [Deepest Leaves Sum](Problems/1302.cpp)                                                          |
 |  1305  |   Medium   | [All Elements in Two Binary Search Trees](Problems/1305.cpp)                                     |