The square map grid is n cells wide and n cells tall. A 1 is land and a 0 is water. Land cells that touch along a side (above, below, left or right, not diagonally) belong to the same island, and the map holds exactly two islands.
You can turn water cells into land, one at a time. Return the fewest water cells you must turn into land so that the two islands become one.
One way: fill row 0 at columns 2, 3 and 4, then row 1 at column 4. That lands next to the second island's top cell at row 2, column 4. No route of three cells reaches across.
The two land cells touch only at a corner, so they are two separate islands. Filling the cell to the right of the middle one (or the one below it) joins them.
The small island in row 3 needs two filled cells either way: straight up from column 1 (rows 2 and 1), or straight right along row 3 (columns 2 and 3).
Constraints
n == grid.length == grid[i].length2 <= n <= 100grid[i][j] is 0 or 1.grid holds exactly two islands.The fewest cells to fill is the shortest distance across water from one island to the other. Search outward from the whole first island at once, not from one cell at a time.
4