1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
const int n = grid1.size(), m = grid1[0].size();
int ds[] = {1, 0, -1, 0, 1};
function<bool(int, int)> dfs = [&](int x, int y) {
grid2[x][y] = 0;
bool ans = true;
if (!grid1[x][y]) ans = false;
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid2[nx][ny] && !dfs(nx, ny))
ans = false;
}
return ans;
};
int ans = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (grid2[i][j] && dfs(i, j))
++ans;
return ans;
}
};
|