Shortest Bridge Between Islands

Problem Statement
You are given an n x n binary matrix grid, where 1 represents land and 0 represents water. An island is a 4-directionally connected group of 1's (up, down, left, right) not connected to any other 1's by these directions. There are exactly two islands in the grid. Return the length of the shortest bridge needed to connect the two islands by flipping some 0's (water) to 1's (land). The length of the bridge is the number of 0's that must be flipped.[1][7]

Approach Tags
This problem uses BFS to find the shortest distance and DFS to identify one island's boundary cells. It treats the matrix as a graph where adjacent cells are nodes.[3][1]

Input/Output Examples

Example 1:
Input:
grid = [[0,1],[1,0]]
Output: 1
Explanation: Flip one water cell to connect the islands.[7][1]

Example 2:
Input:
grid = [[0,1,0], [0,0,0], [0,0,1]]
Output: 2
Explanation: Flip two water cells (e.g., grid and grid) to form a bridge.[2][1][7]

Example 3:
Input:
grid = [[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]]
Output: 1
Explanation: The islands are already nearly connected; flip one 0 adjacent to both.[1]

Constraints

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.[7][1]