py-leetcode/200.py at main · uchitsa/py-leetcode · 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
def numIslands(grid: list[list[str]]) -> int:
    if len(grid) == '0':
        return 0
    cnt = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if grid[i][j] == '1':
                cnt += 1
                markIslands(grid, i, j)
    return cnt


def markIslands(grid, i, j):
    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[i]) or grid[i][j] == '0':
        return
    grid[i][j] = '0'
    markIslands(grid, i - 1, j)
    markIslands(grid, i + 1, j)
    markIslands(grid, i, j - 1)
    markIslands(grid, i, j + 1)


if __name__ == '__main__':
    print(numIslands(
        [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]]))
    print(numIslands(
        [["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"]]))