leetcode

commit 1c5c912fcef26b4a5a3b14534dcc94149bd47a20
parent b0a5a3da4551a99057f6694e0981d1109203cf27
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri,  7 Apr 2023 10:38:18 +0200

Daily Problem

Diffstat:
A
Problems/1020.cpp
 | 
37
+++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 38 insertions(+), 0 deletions(-)
diff --git a/Problems/1020.cpp b/Problems/1020.cpp
@@ -0,0 +1,37 @@
+class Solution {
+  int n, m;
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+  int flood_fill(vector<vector<int>> &grid, int x, int y) {
+    grid[x][y] = 0;
+    int count = 1;
+    if (valid(x + 1, y) && grid[x + 1][y]) count += flood_fill(grid, x + 1, y);
+    if (valid(x - 1, y) && grid[x - 1][y]) count += flood_fill(grid, x - 1, y);
+    if (valid(x, y + 1) && grid[x][y + 1]) count += flood_fill(grid, x, y + 1);
+    if (valid(x, y - 1) && grid[x][y - 1]) count += flood_fill(grid, x, y - 1);
+    return count;
+  }
+
+public:
+  int numEnclaves(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;
+        res += flood_fill(grid, i, j);
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -380,6 +380,7 @@ for solving problems.
 |  1011  |   Medium   | [Capacity To Ship Packages Within D Days](Problems/1011.cpp)                                     |
 |  1014  |   Medium   | [Best Sightseeing Pair](Problems/1014.cpp)                                                       |
 |  1019  |   Medium   | [Next Greater Node In Linked List](Problems/1019.cpp)                                            |
+|  1020  |   Medium   | [Number of Enclaves](Problems/1020.cpp)                                                          |
 |  1022  |    Easy    | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp)                                          |
 |  1026  |   Medium   | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp)                                |
 |  1038  |   Medium   | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp)                                      |