We are given an $n×n$ binary matrix grid containing 0s and 1s. Each cell in the grid represents either land or water. A cell with a value of 1 represents land, while a cell with a value of 0 represents water. A group of adjacent cells with a value of 1 constitutes an island. Two cells are considered adjacent if one is above, below, to the left, or to the right of the other. Our task is to return the smallest number of 0s we must flip to connect the two islands.

Note: We may assume all four edges of the grid are surrounded by water.

Constraints:

• $2$ $\leq$ n $\leq$ $20$

• $n ==$ grid.length $==$ grid[i].length.

• grid[i][j] is either 0 or 1.

• There are exactly two islands in the grid.

The solution for finding the shortest bridge between two islands in a grid involves a two-step process using Breadth-First Search (BFS) and queues. First, we locate and mark one of the islands by performing BFS. During this step, we use a queue to explore and mark all the cells of the first island to keep track of the entire island as the starting point for the next phase.

In the second phase, we expand outward from the marked island using another BFS. We initialize a new queue with the coordinates of the first island’s boundary cells. As we explore each cell, we mark it as visited to avoid revisiting. The BFS expands layer by layer, crossing the water (0s) and keeping track of the number of layers (or distance) crossed. The first time we encounter a cell that belongs to the second island, the BFS stops, and the number of layers crossed represents the length of the shortest bridge. This approach ensures we find the minimal number of 0s required to connect the two islands.

Below are the steps of the algorithm:

1. Initial setup

   1. Iterate over the grid to find the first land cell. Once found, assume this cell belongs to Island A. Let’s call this cell grid[first_x][first_y].

   2. Initialize three lists:

      1. bfs_queue: to keep track of cells belonging to Island A during BFS.

      2. new_bfs: to gather cells for the next round of BFS.

      3. second_bfs_queue: to store cells for searching the shortest distance to Island B.

2. Identify island A

   1. Perform BFS starting from grid[first_x][first_y] to explore all cells of Island A and add them to bfs_queue.

   2. For each cell grid[x][y] in bfs_queue:

      1. If the cell is part of Island A (grid[x][y] = 1):

         1. Mark the cell as visited by setting its value to $2$.

         2. Add the cell to new_bfs for further BFS exploration.

         3. Add the cell to second_bfs_queue to later search for the shortest path to Island B.

3. Expand BFS

   1. If new_bfs is not empty, add all its cells to bfs_queue and repeat the BFS process to fully identify Island A.

   2. Once all cells of Island A are identified, proceed to the next step.

4. Search for the Shortest Bridge

   1. Initialize distance = 0 to track the number of flips needed.

   2. Perform BFS on the cells in second_bfs_queue to find those cells that lie in the first layer of neighbors. Initially, second_bfs_queue represents the cells of Island A. In later iterations, it represents the neighboring layer of cells discovered recently.

   3. For each cell (x, y) in second_bfs_queue:

      1. If the cell belongs to Island B (grid[x][y] = 1), return the current distance as the shortest path.

      2. If the cell is water (grid[x][y] = 0), mark it as visited by setting its value to $-1$ and add it to new_bfs for further exploration.

5. Repeat and expand

   1. After processing all cells in the current layer, add all the cells from new_bfs to second_bfs_queue, increment distance by $1$, and repeat the BFS until you reach Island B.

Let’s look at the following illustration to get a better understanding of the solution: