Pattern visualizer
Making a Large Island
Trying every flip and re-measuring its island from scratch is wasted work, because most flips reuse the same two or three islands over and over. Label each island once instead — a flood fill per unlabelled land cell, tagging every cell it reaches with that island's id — and store each island's area against its label. Now a water cell's best possible flip is arithmetic: look at its up-to-four land neighbours, collect the DISTINCT island labels among them (a cell can touch the same island twice through two different neighbours, and that must only count once), and add 1 for the cell itself to the sum of those islands' areas. The largest such sum, or the largest island already on the board if no flip helps, is the answer. Animated on: grid = [[1,1,0],[0,0,1],[0,1,1]] — flip exactly one water cell to land to make the largest possible island..
Label every island once, then let each water cell add up its neighbours
3x3 grid, drawn as one vertex per cell
9 cells, 5 of them land. Exactly one water cell may flip to land — the question is which flip merges the most area, so every water cell's land neighbours matter, not just the islands on their own.
1FUNCTION largestIsland(grid):2 label <- 23 area <- EMPTY MAP4 FOR EACH CELL (r, c) IN grid5 IF grid[r][c] = 1 AND labelOf[r][c] = 06 area[label] <- FLOODFILL(r, c, label)7 label <- label + 18 best <- MAX(area VALUES) OR 09 FOR EACH CELL (r, c) IN grid10 IF grid[r][c] = 011 seen <- DISTINCT LABELS OF NEIGHBOURS(r, c)12 best <- MAX(best, 1 + SUM(area[l] FOR l IN seen))13 RETURN best
← / → step · space play · Home restart