Shortest Bridge

Given a binary grid containing exactly two islands, return the minimum number of 0s that must be flipped to connect the two islands. Pattern focus: Multi-Source BFS. Mark one island first, then expand from its boundary cells until the second island is reached.

Input Format

grid = binary matrix with exactly two islands

Output Format

minimum number of flips needed to connect the islands

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • grid must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

1

Explanation:

Flipping one water cell connects the islands.

Example 2:

Input:

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

Output:

2

Explanation:

Two flips connect the islands by the shortest route.

Loading...
Shortest Bridge - Queue Deque DSA Problem