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]]))
|