Shortest Bridge

Problem

Given a grid with exactly two islands of 1s, return the fewest 0 cells that must be flipped to connect them.

Flood fill the first island, then run a multi-source BFS from all of its cells through water until land of the second island is reached. The number of expanding layers equals the number of flips.

Hint

Marking visited cells as water prevents the BFS from entering the same cell twice.

Test cases

case 1

in: [[[0,1],[1,0]]]

expected: 1

case 2

in: [[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]]

expected: 1

case 3

in: [[[1,0,1]]]

expected: 1

case 4

in: [[[1,0,0],[0,0,0],[0,0,1]]]

expected: 3

case 5

in: [[[1,1,0],[0,0,0],[0,1,1]]]

expected: 1

Starter codePython

def shortest_bridge(grid):
    # Your code here
    pass

5 test cases · run your code against them in the editor