diff options
author | Jack Sangdahl <[email protected]> | 2024-08-28 01:15:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-28 01:15:13 -0600 |
commit | 35132e9f44831f0cf18d329b15482744bd5548de (patch) | |
tree | 9d23b05d230ca2a557e42274b87a32b48131159a | |
parent | dfbbbbb78851f50c9f20a102f2f56c047046aab7 (diff) | |
download | leetcode-35132e9f44831f0cf18d329b15482744bd5548de.tar.gz leetcode-35132e9f44831f0cf18d329b15482744bd5548de.zip |
1905. count sub islands
-rw-r--r-- | count_sub_islands.c | 87 | ||||
-rw-r--r-- | count_sub_islands.py | 72 |
2 files changed, 159 insertions, 0 deletions
diff --git a/count_sub_islands.c b/count_sub_islands.c new file mode 100644 index 0000000..acfc0e9 --- /dev/null +++ b/count_sub_islands.c @@ -0,0 +1,87 @@ +// 1905. Count Sub Islands +#include "leetcode.h" + +/* + * you are given two 'm * n' binary matricies 'grid1', and 'grid2' containing + * only 0's (represeting water) and 1's (representing land). an island is a + * group of 1's connected 4 directionally (horizontal or vertical). any cells + * outside of the grid are considered water cells. an island in 'grid2' is + * considered a sub-island if there is an island in 'grid1' that contains all + * the cells that make up this island is 'grid2'. return the number of islands + * in 'grid2' that are considered sub islands + */ + +int countSubIslands(int **grid1, int grid1Size, int *grid1ColSize, int **grid2, + int grid2Size, int *grid2ColSize) { + const int row = grid1Size, col = *grid1ColSize; + int cnt = 0, head, tail; + struct point { + int row, col; + } bfs_queue[col * row]; + for (int i = 0; i < row; i++) { + for (int j = 0; j < col; j++) { + if (!grid2[i][j]) + continue; + bool matched = true; + head = 0; + grid2[i][j] = 0; + bfs_queue[0].row = i; + bfs_queue[0].col = j; + tail = 1; + do { + const struct point curr = bfs_queue[head]; + head++; + if (!grid1[curr.row][curr.col]) + matched = false; + static const struct point offsets[] = { + {-1, 0}, {0, 1}, {1, 0}, {0, -1}}; + for (int k = 0; k < sizeof(offsets) / sizeof(offsets[0]); k++) { + const struct point next = {curr.row + offsets[k].row, + curr.col + offsets[k].col}; + if ((next.row >= 0 && next.row < row) && + (next.col >= 0 && next.col < col) && grid2[next.row][next.col]) { + grid2[next.row][next.col] = 0; + bfs_queue[tail] = next; + tail++; + } + } + } while (head < tail); + if (matched) + cnt++; + } + } + return cnt; +} + +int main() { + int g11[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}}, + g11cs = 5; + int g21[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}}, + g21cs = 5; + int g12[5][5] = {{1, 0, 1, 0, 1}, + {1, 1, 1, 1, 1}, + {0, 0, 0, 0, 0}, + {1, 1, 1, 1, 1}, + {1, 0, 1, 0, 1}}, + g12cs = 5; + int g22[5][5] = {{0, 0, 0, 0, 0}, + {1, 1, 1, 1, 1}, + {0, 1, 0, 1, 0}, + {0, 1, 0, 1, 0}, + {1, 0, 0, 0, 1}}, + g22cs = 5; + printf("%d\n", + countSubIslands((int **)g11, ARRAY_SIZE(g11), &g11cs, (int **)g21, + ARRAY_SIZE(g21), &g21cs)); // expect: 3 + printf("%d\n", + countSubIslands((int **)g12, ARRAY_SIZE(g12), &g12cs, (int **)g22, + ARRAY_SIZE(g22), &g22cs)); // expect: 2 +} diff --git a/count_sub_islands.py b/count_sub_islands.py new file mode 100644 index 0000000..b701863 --- /dev/null +++ b/count_sub_islands.py @@ -0,0 +1,72 @@ +# 1905. Count Sub Islands + +""" +you are given two 'm * n' binary matricies 'grid1', and 'grid2' containing +only 0's (represeting water) and 1's (representing land). an island is a +group of 1's connected 4 directionally (horizontal or vertical). any cells +outside of the grid are considered water cells. an island in 'grid2' is +considered a sub-island if there is an island in 'grid1' that contains all +the cells that make up this island is 'grid2'. return the number of islands +in 'grid2' that are considered sub islands +""" + + +class Solution(object): + def countSubIslands(self, grid1, grid2): + """ + :type grid1: List[List[int]] + :type grid2: List[List[int]] + :rtype: int + """ + n, m = len(grid1), len(grid1[0]) + + def dfs(i, j): + if not (0 <= i < n and 0 <= j < m and grid1[i][j] == 1): + return 1 + grid1[i][j] = 0 + res = grid2[i][j] + for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]: + res &= dfs(i + di, j + dj) + return res + + return sum(dfs(i, j) for i in range(n) for j in range(m) if grid1[i][j]) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.countSubIslands( + 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], + ], + 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], + ], + ) + ) + print( + obj.countSubIslands( + grid1=[ + [1, 0, 1, 0, 1], + [1, 1, 1, 1, 1], + [0, 0, 0, 0, 0], + [1, 1, 1, 1, 1], + [1, 0, 1, 0, 1], + ], + grid2=[ + [0, 0, 0, 0, 0], + [1, 1, 1, 1, 1], + [0, 1, 0, 1, 0], + [0, 1, 0, 1, 0], + [1, 0, 0, 0, 1], + ], + ) + ) |