aboutsummaryrefslogtreecommitdiff
path: root/min_num_days_disconnect_island.py
blob: 14dfd44482a05e294e3c42d4748a3ad0a938a6a4 (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
# 1568. Minimum Number of Days to Disconnect Island

"""
you are given an 'm * n' binary grid where 1 repansents land and 0 repansents
water. an island is a maximal 4 directionally horizontal or vertical
connected group of 1's. the grid is said to be connected if we have exactly
one island otherwise it is disconnected. in one day, we are allowed to change
any single land cell 1 into a water cell 0. return the minimum number of days
to disconnect the grid.
"""


class Solution(object):
    def minDays(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        cnt = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]:
                    cnt += 1
                    root = (i, j)
        if cnt <= 1:
            return cnt
        vis, low, time, ans = {root}, {}, {}, []

        def articulation_points(curr, parent):
            low[curr] = time[curr] = len(vis)
            children = 0
            i, j = curr
            for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if (x, y) == parent:
                    continue
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y]:
                    if (x, y) not in vis:
                        vis.add((x, y))
                        articulation_points((x, y), curr)
                        low[curr] = min(low[curr], low[(x, y)])
                        children += 1
                        if low[(x, y)] >= time[(curr)] and parent != (-1, -1):
                            ans.append([i, j])
                    else:
                        low[curr] = min(low[curr], time[(x, y)])

                if parent == (-1, -1) and children > 1:
                    ans.append([x, y])

        articulation_points(root, (-1, -1))
        if len(vis) != cnt:
            return 0
        elif ans:
            return 1
        else:
            return 2


if __name__ == "__main__":
    obj = Solution()
    print(obj.minDays(grid=[[0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]))
    print(obj.minDays(grid=[[1, 1]]))