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.
1public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(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]++;
}
}
}
}
public class Solution {
public int CountSubIslands(int[][] grid1, int[][] grid2) {
int m = grid1.Length, n = grid1[0].Length;
UnionFind uf = new UnionFind(m * n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid1[i][j] == 1) {
int index = i * n + j;
if (i + 1 < m && grid1[i + 1][j] == 1) uf.Union(index, (i + 1) * n + j);
if (j + 1 < n && grid1[i][j + 1] == 1) uf.Union(index, i * n + j + 1);
}
}
}
bool[] rootVisited = new bool[m * n];
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid2[i][j] == 1) {
int index = i * n + j;
int rootIndex = uf.Find(index);
if (!rootVisited[rootIndex]) {
bool isSubIsland = true;
var directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} };
var stack = new Stack<int[]>();
stack.Push(new int[] {i, j});
while (stack.Count > 0) {
var point = stack.Pop();
foreach (var dir in directions) {
int newX = point[0] + dir[0];
int newY = point[1] + dir[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid2[newX][newY] == 1) {
grid2[newX][newY] = 0;
if (uf.Find(newX * n + newY) != rootIndex) {
isSubIsland = false;
} else {
stack.Push(new int[] {newX, newY});
}
}
}
}
if (isSubIsland) {
rootVisited[rootIndex] = true;
count++;
}
}
}
}
}
return count;
}
public static void Main(string[] args) {
int[][] grid1 = {
new int[] {1, 1, 1, 0, 0},
new int[] {0, 1, 1, 1, 1},
new int[] {0, 0, 0, 0, 0},
new int[] {1, 0, 0, 0, 0},
new int[] {1, 1, 0, 1, 1}
};
int[][] grid2 = {
new int[] {1, 1, 1, 0, 0},
new int[] {0, 0, 1, 1, 1},
new int[] {0, 1, 0, 0, 0},
new int[] {1, 0, 1, 1, 0},
new int[] {0, 1, 0, 1, 0}
};
Solution sol = new Solution();
Console.WriteLine(sol.CountSubIslands(grid1, grid2));
}
}The C# program utilizes a Union-Find class to group islands and test their containment correspondence between the two grids, culminating in determining the number of sub-islands present.