Causeway Between Two Islands

Medium

A map is given as a square grid grid of size n × n, where 1 is land and 0 is water. An island is a group of land cells connected through their sides (not diagonally). The map has exactly two islands. To join them you may fill water cells, turning them into land. Return the smallest number of cells you must fill so that the two islands become one.

Example 1

grid=[[1, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 1]] → 3

For example, fill (1, 1), (1, 2) and (2, 2): three water cells link the island in the top-left corner with the one in the bottom right. Fewer is not enough.

Example 2

grid=[[1, 0, 1], [1, 0, 1], [1, 0, 1]] → 1

Two vertical strips of land are split by a single water column, so filling one cell is enough.

Constraints

n == len(grid) == len(grid[i])
2 ≤ n ≤ 200
grid[i][j] is 0 or 1
The map contains exactly two islands

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Rain Reaching Both Seas Medium Can the Ball Stop at the Target Medium Shortest Path of a Rolling Ball Medium

Input

grid=[[1, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 0, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 16 tests on the server, hidden ones included.