Algorithms/num_is_islands.py at main · Dr-Code-lab/Algorithms · GitHub

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
class CountIslands():
    from typing import List
    def __init__ (self, content = [[1,2,3],[4,5,6],[7,8,9]]):
        self.content = content
        print(content, '\n')

    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(row, column):
            if row < 0 or column < 0 or row == rows or column == columns:
                return
            if grid[row][column] != '1':  # There is land
                return

            grid[row][column] = '*' # Mark visited lands
            dfs(row-1, column)
            dfs(row+1, column)
            dfs(row, column+1)
            dfs(row, column-1)

        num_of_isls = 0
        rows = len(grid)
        columns = len(grid[0])

        for row in range(rows):
            for column in range(columns):
                if grid[row][column] == '1':
                    dfs(row, column)
                    num_of_isls += 1

        return num_of_isls


    def main(self):
        result = self.numIslands(self.content)
        if result:
            print('\033[92m',result, '\033[0m\n........')
        else:
            print('\033[91m',result, '\033[0m\n........')

    # TEST :
if __name__ == '__main__':

    args = (
            [["0","1","1","1","0"],
             ["1","0","0","1","0"],
             ["1","1","0","0","0"],
             ["0","0","0","0","0"]],

            [["1","1","1","1","0"],
             ["1","1","0","1","0"],
             ["1","1","0","0","0"],
             ["0","0","0","0","0"]],

            [["1","1","0","0","0"],
             ["1","1","0","0","0"],
             ["0","0","1","0","0"],
             ["0","0","0","1","1"]],

            [["0","1","0","0","1"],
             ["1","0","0","0","0"],
             ["0","0","1","0","0"],
             ["0","0","0","1","1"]]
            )

    for item in args:
        CountIslands(item).main()