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 <vector>
2using namespace std;
3
4void dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int i, int j, bool& isSubIsland) {
5 if (i < 0 || i >= grid2.size() || j < 0 || j >= grid2[0].size() || grid2[i][j] == 0) {
6 return;
7 }
8 if (grid1[i][j] == 0) {
9 isSubIsland = false;
10 }
11 grid2[i][j] = 0;
12 dfs(grid1, grid2, i+1, j, isSubIsland);
13 dfs(grid1, grid2, i-1, j, isSubIsland);
14 dfs(grid1, grid2, i, j+1, isSubIsland);
15 dfs(grid1, grid2, i, j-1, isSubIsland);
16}
17
18int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
19 int m = grid1.size(), n = grid1[0].size(), 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, i, j, isSubIsland);
25 if (isSubIsland) count++;
26 }
27 }
28 }
29 return count;
30}
31
32int main() {
33 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}};
34 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}};
35 int result = countSubIslands(grid1, grid2);
36 cout << result << endl;
37 return 0;
38}The solution finds islands in grid2 and uses DFS to explore them while checking if they are contained within an island in grid1. If at any point a part of an island in grid2 is found to be not part of an island in grid1, the island in grid2 is disqualified as a sub-island.
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 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.