Problems/934. Shortest Bridge

934. Shortest Bridge

MediumMatrixGraphDFSBFS

You are given an m x n binary grid where 1 represents land and 0 represents water. The grid contains exactly two distinct islands.

You want to connect these two islands by changing a minimum number of water cells (0s) to land cells (1s). Find and return the minimum number of 0s you must flip to connect the two islands into one single component.

Example 1

Input: grid = [ [0, 1, 0], [0, 0, 0], [0, 0, 1] ]

Output: 2

We can flip grid[1][1] and grid[0][2] (or grid[1][2]) to connect the two islands with a bridge of length 2.

Example 2

Input: grid = [ [1, 0], [0, 1] ]

Output: 1

Flipping either (0,1) or (1,0) creates a path between the two corner land cells, which takes 1 flip.

Example 3

Input: grid = [ [1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1] ]

Output: 3

Flipping water cells at (1,1), (1,2), (1,3) connects the top-left island to the bottom-right island.

Visualizer

⌥

Visualizer will appear here