Pattern visualizer
Minimum Number of Days to Disconnect Island
Turn the grid into a graph first: one node per land cell, one edge between every pair of orthogonally adjacent land cells. Disconnecting the island is now just about REMOVING NODES from that graph. It only ever takes at most 2 removals to disconnect any grid island, so the whole problem collapses into three checks in increasing order: is it already not one piece (0)? Does removing any single cell split it (1)? If neither, the answer is 2. This 2x2 block of land is a 4-node cycle, where every node has exactly two neighbours — the textbook case where one removal is never enough. Animated on: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] — each day one land cell (1) can be turned to water (0). What is the minimum number of days until the land is no longer a single connected island?.
Model the island as a graph, then try removing one land cell at a time
The island as a graph
Each land cell becomes a node; an edge joins two nodes only when their grid cells are orthogonally adjacent. This 2x2 block of land turns into a 4-node cycle — every cell has exactly two neighbours, which is exactly the shape that resists being split by removing just one of them.
1FUNCTION minDays(grid):2 comps <- COUNT_COMPONENTS(grid, NONE)3 IF comps != 14 RETURN 05 FOR EACH land cell (r, c) IN grid6 comps <- COUNT_COMPONENTS(grid, REMOVE (r, c))7 IF comps = 18 CONTINUE9 RETURN 110 RETURN 2
← / → step · space play · Home restart