-
Notifications
You must be signed in to change notification settings - Fork 0
/
1905. Count Sub Islands.cpp
45 lines (36 loc) · 1.05 KB
/
1905. Count Sub Islands.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// https://leetcode.com/problems/count-sub-islands/
class Solution
{
bool isSubIsland = true;
public:
int countSubIslands(vector<vector<int>> &grid1, vector<vector<int>> &grid2)
{
int result = 0;
for (int i = 0; i < grid2.size(); ++i)
{
for (int j = 0; j < grid2[i].size(); ++j)
{
if (grid2[i][j] == 1)
{
isSubIsland = true;
DFS(grid1, grid2, i, j);
if (isSubIsland)
result++;
}
}
}
return result;
}
void DFS(vector<vector<int>> &grid1, vector<vector<int>> &grid2, int i, int j)
{
if (i < 0 || i >= grid2.size() || j < 0 || j >= grid2[i].size() || grid2[i][j] == 0)
return;
if (grid1[i][j] == 0)
isSubIsland = false;
grid2[i][j] = 0;
DFS(grid1, grid2, i + 1, j);
DFS(grid1, grid2, i - 1, j);
DFS(grid1, grid2, i, j + 1);
DFS(grid1, grid2, i, j - 1);
}
};