leetcode-solution/Python/0200-number-of-islands.py at main · hogan-tech/leetcode-solution · 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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# time complexity: O(m*n)
# space complexity: O(m*n)
from collections import deque
from typing import List


class Solution:
    def dfs(self, grid: List[List[str]], r: int, c: int) -> None:
        nR = len(grid)
        nC = len(grid[0])
        grid[r][c] = '0'
        if r - 1 >= 0 and grid[r - 1][c] == "1":
            self.dfs(grid, r - 1, c)
        if r + 1 < nR and grid[r + 1][c] == "1":
            self.dfs(grid, r + 1, c)
        if c - 1 >= 0 and grid[r][c - 1] == "1":
            self.dfs(grid, r, c - 1)
        if c + 1 < nC and grid[r][c + 1] == "1":
            self.dfs(grid, r, c + 1)

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        numIslands = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    numIslands += 1
                    self.dfs(grid, r, c)
        return numIslands


class UnionFind:
    def __init__(self, grid):
        self.parent = []
        self.rank = []
        self.count = 0
        ROW = len(grid)
        COL = len(grid[0])
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == '1':
                    self.parent.append(r * COL + c)
                    self.count += 1
                else:
                    self.parent.append(-1)
                self.rank.append(0)

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return True
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        elif self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        self.count -= 1

    def getCount(self):
        return self.count


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW = len(grid)
        COL = len(grid[0])
        unionFind = UnionFind(grid)
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == '1':
                    grid[r][c] = '0'
                    if r + 1 < ROW and grid[r + 1][c] == '1':
                        unionFind.union(r * COL + c, (r + 1) * COL + c)
                    if c + 1 < COL and grid[r][c + 1] == '1':
                        unionFind.union(r * COL + c, r * COL + c + 1)
        count = unionFind.getCount()
        return count


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ROW = len(grid)
        COL = len(grid[0])

        def bfs(r, c):
            queue = deque()
            queue.append((r, c))
            while queue:
                currR, currC = queue.popleft()
                grid[currR][currC] = '0'
                for dR, dC in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    nextR = currR + dR
                    nextC = currC + dC
                    if 0 <= nextR < ROW and 0 <= nextC < COL and grid[nextR][nextC] == '1':
                        grid[nextR][nextC] = '0'
                        queue.append((nextR, nextC))

        count = 0
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == '1':
                    count += 1
                    bfs(r, c)

        return count


grid = [
    ["1", "1", "1", "1", "0"],
    ["1", "1", "0", "1", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "0", "0", "0"]
]
print(Solution().numIslands(grid))
grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]
print(Solution().numIslands(grid))