aboutsummaryrefslogtreecommitdiff
path: root/count_sub_islands.py
blob: b701863a4eb8f7cef7e1d52a99b5cb1317374dda (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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],
            ],
        )
    )