diff options
Diffstat (limited to 'count_sub_islands.py')
-rw-r--r-- | count_sub_islands.py | 72 |
1 files changed, 72 insertions, 0 deletions
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], + ], + ) + ) |