Description
You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally connected group of 1s. There are exactly two islands in grid. Return the smallest number of 0s you must flip to connect the two islands.
Examples
grid = [[0,1],[1,0]]1Flip one 0 to connect islands.
grid = [[1]]1Minimal case with a single-element matrix.
grid = [[1,1,1,0,0],[1,0,0,0,0],[1,0,0,0,1],[0,0,0,1,1],[0,0,0,1,1]]2The first island is the L-shaped group of 1s in the top-left (positions [0,0], [0,1], [0,2], [1,0], [2,0]). The second island is the square group of 1s in the bottom-right (positions [2,4], [3,3], [3,4], [4,3], [4,4]). To connect these islands with the minimum number of flips, the task requires flip 2 zeros: it is possible to flip [2,1] and [2,2] to create a bridge from [2,0] to [2,3], or flip [1,3] and [2,3] to create a different path. Either way, the minimum is 2 flips.
Constraints
- •
n == grid.length == grid[i].length - •
2 ≤ n ≤ 100 - •
grid[i][j] is either 0 or 1