Sponsored
Sponsored
This approach uses Depth-First Search (DFS) to explore each island in grid2, checking if it matches an area in grid1. We iterate through each cell in grid2, initiating a DFS whenever we encounter land (1). During DFS, we verify if the entire island in grid2 can be found in grid1. If during exploration, we encounter a cell that is 1 in grid2 but 0 in grid1, we mark it as not a sub-island.
Time Complexity: O(m * n), where m and n are the dimensions of the grids, as each cell is visited a constant number of times.
Space Complexity: O(1) additional space not counting input and stack space for recursion.
1#include <stdbool.h>
2#include <stdio.h>
3
4void dfs(int** grid1, int** grid2, int m, int n, int i, int j, bool* isSubIsland) {
5 if (i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0) {
6 return;
7 }
8 if (grid1[i][j] == 0) {
9 *isSubIsland = false;
10 }
11 grid2[i][j] = 0;
12 int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
13 for (int d = 0; d < 4; d++) {
14 dfs(grid1, grid2, m, n, i + dirs[d][0], j + dirs[d][1], isSubIsland);
15 }
16}
17
18int countSubIslands(int** grid1, int grid1Size, int* grid1ColSize, int** grid2, int grid2Size, int* grid2ColSize) {
19 int m = grid1Size, n = grid1ColSize[0], count = 0;
20 for (int i = 0; i < m; i++) {
21 for (int j = 0; j < n; j++) {
22 if (grid2[i][j] == 1) {
23 bool isSubIsland = true;
24 dfs(grid1, grid2, m, n, i, j, &isSubIsland);
25 if (isSubIsland) count++;
26 }
27 }
28 }
29 return count;
30}
31
32int main() {
33 int grid1[5][5] = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}};
34 int grid2[5][5] = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};
35 int grid1ColSize[] = {5,5,5,5,5};
36 int grid2ColSize[] = {5,5,5,5,5};
37 int* grid1Ptrs[5];
38 int* grid2Ptrs[5];
39 for(int i = 0; i < 5; i++) {
40 grid1Ptrs[i] = grid1[i];
41 grid2Ptrs[i] = grid2[i];
42 }
43 int result = countSubIslands(grid1Ptrs, 5, grid1ColSize, grid2Ptrs, 5, grid2ColSize);
44 printf("%d\n", result);
45 return 0;
46}We first traverse all cells in grid2. Upon encountering a cell that is part of an island (i.e., its value is 1), we start a DFS to explore the entire structure connected to this cell. During this DFS, for every cell in the current island of grid2, we check if corresponding cells in grid1 are also land. If we find a water cell (0) in grid1 where there's land in grid2, we set isSubIsland to false. If DFS completes and isSubIsland remains true, we increment our count of sub-islands.
This approach uses the Union-Find data structure to efficiently group connected islands. By initially identifying all islands in both grids, we can ascertain the sub-islands by ensuring that connected components (islands) in grid2 are completely represented within connected components in grid1.
Time Complexity: O(m * n * (α(m*n))), where α is the Inverse Ackermann function, a very slow-growing function.
Space Complexity: O(m * n) to store the parent and rank arrays.
1#include <vector>
using namespace std;
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
for (int i = 0; i < size; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
private:
vector<int> parent;
vector<int> rank;
};
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
int m = grid1.size(), n = grid1[0].size();
UnionFind uf(m * n);
auto getIndex = [&](int x, int y) -> int {
return x * n + y;
};
// Union for grid1
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid1[i][j] == 1) {
for (const auto& d : vector<pair<int, int>>{{1, 0}, {0, 1}}) {
int ni = i + d.first, nj = j + d.second;
if (ni < m && nj < n && grid1[ni][nj] == 1) {
uf.unite(getIndex(i, j), getIndex(ni, nj));
}
}
}
}
}
vector<bool> found(m * n, false);
int count = 0;
// Check for grid2
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid2[i][j] == 1) {
bool isSubIsland = true;
int root = uf.find(getIndex(i, j));
if (!found[root]) {
for (const auto& d : vector<pair<int, int>>{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) {
int ni = i + d.first, nj = j + d.second;
if (ni >= 0 && nj >= 0 && ni < m && nj < n && grid2[ni][nj] == 1) {
if (uf.find(getIndex(i, j)) != uf.find(getIndex(ni, nj))) {
isSubIsland = false;
}
}
}
if (isSubIsland) {
found[root] = true;
count++;
}
}
}
}
}
return count;
}
int main() {
vector<vector<int>> grid1 = {{1,1,1,0,0},{0,1,1,1,1},{0,0,0,0,0},{1,0,0,0,0},{1,1,0,1,1}};
vector<vector<int>> grid2 = {{1,1,1,0,0},{0,0,1,1,1},{0,1,0,0,0},{1,0,1,1,0},{0,1,0,1,0}};
cout << countSubIslands(grid1, grid2) << endl;
return 0;
}This C++ solution leverages the Union-Find (Disjoint Set) structure to efficiently find and merge islands (connected components) within grid1. Once connected components are established for grid1, islands in grid2 are checked for eligibility as sub-islands based on component containment.