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.
By utilizing DFS in Python, we iterate over grid2 to identify starting points of islands, and traverse them to assess if each corresponds entirely within islands in grid1, consequently counting valid 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 {
2 private int[] parent;
3 private int[] rank;
4
5 public UnionFind(int size) {
6 parent = new int[size];
7 rank = new int[size];
8 for (int i = 0; i < size; i++) {
9 parent[i] = i;
10 rank[i] = 0;
11 }
12 }
13
14 public int Find(int x) {
15 if (parent[x] != x) {
16 parent[x] = Find(parent[x]);
17 }
18 return parent[x];
19 }
20
21 public void Union(int x, int y) {
22 int rootX = Find(x);
23 int rootY = Find(y);
24 if (rootX != rootY) {
25 if (rank[rootX] > rank[rootY]) {
26 parent[rootY] = rootX;
27 } else if (rank[rootX] < rank[rootY]) {
28 parent[rootX] = rootY;
29 } else {
30 parent[rootY] = rootX;
31 rank[rootX]++;
32 }
33 }
34 }
35}
36
37public class Solution {
38 public int CountSubIslands(int[][] grid1, int[][] grid2) {
39 int m = grid1.Length, n = grid1[0].Length;
40 UnionFind uf = new UnionFind(m * n);
41
42 for (int i = 0; i < m; i++) {
43 for (int j = 0; j < n; j++) {
44 if (grid1[i][j] == 1) {
45 int index = i * n + j;
46 if (i + 1 < m && grid1[i + 1][j] == 1) uf.Union(index, (i + 1) * n + j);
47 if (j + 1 < n && grid1[i][j + 1] == 1) uf.Union(index, i * n + j + 1);
48 }
49 }
50 }
51
52 bool[] rootVisited = new bool[m * n];
53 int count = 0;
54
55 for (int i = 0; i < m; i++) {
56 for (int j = 0; j < n; j++) {
57 if (grid2[i][j] == 1) {
58 int index = i * n + j;
59 int rootIndex = uf.Find(index);
60 if (!rootVisited[rootIndex]) {
61 bool isSubIsland = true;
62 var directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} };
63 var stack = new Stack<int[]>();
64 stack.Push(new int[] {i, j});
65 while (stack.Count > 0) {
66 var point = stack.Pop();
67 foreach (var dir in directions) {
68 int newX = point[0] + dir[0];
69 int newY = point[1] + dir[1];
70 if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid2[newX][newY] == 1) {
71 grid2[newX][newY] = 0;
72 if (uf.Find(newX * n + newY) != rootIndex) {
73 isSubIsland = false;
74 } else {
75 stack.Push(new int[] {newX, newY});
76 }
77 }
78 }
79 }
80 if (isSubIsland) {
81 rootVisited[rootIndex] = true;
82 count++;
83 }
84 }
85 }
86 }
87 }
88
89 return count;
90 }
91
92 public static void Main(string[] args) {
93 int[][] grid1 = {
94 new int[] {1, 1, 1, 0, 0},
95 new int[] {0, 1, 1, 1, 1},
96 new int[] {0, 0, 0, 0, 0},
97 new int[] {1, 0, 0, 0, 0},
98 new int[] {1, 1, 0, 1, 1}
99 };
100 int[][] grid2 = {
101 new int[] {1, 1, 1, 0, 0},
102 new int[] {0, 0, 1, 1, 1},
103 new int[] {0, 1, 0, 0, 0},
104 new int[] {1, 0, 1, 1, 0},
105 new int[] {0, 1, 0, 1, 0}
106 };
107 Solution sol = new Solution();
108 Console.WriteLine(sol.CountSubIslands(grid1, grid2));
109 }
110}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.