aboutsummaryrefslogtreecommitdiff
path: root/min_num_days_disconnect_island.py
diff options
context:
space:
mode:
Diffstat (limited to 'min_num_days_disconnect_island.py')
-rw-r--r--min_num_days_disconnect_island.py62
1 files changed, 62 insertions, 0 deletions
diff --git a/min_num_days_disconnect_island.py b/min_num_days_disconnect_island.py
new file mode 100644
index 0000000..14dfd44
--- /dev/null
+++ b/min_num_days_disconnect_island.py
@@ -0,0 +1,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]]))