> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/34.-shortest-bridge.md).

# 34. Shortest Bridge

In a given 2D binary array `grid`, there are two islands.  (An island is a 4-directionally connected group of `1`s not connected to any other 1s.)

Now, we may change `0`s to `1`s so as to connect the two islands together to form 1 island.

Return the smallest number of `0`s that must be flipped.  (It is guaranteed that the answer is at least 1.)

**Example 1:**

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

**Example 2:**

```
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
```

**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
```

## Solution: (BFS  + DFS)

```cpp
class Solution
{
public:
    queue<pair<int, pair<int, int>>> q;

    void dfs(int i, int j, vector<vector<bool>> &vs, vector<vector<int>> &v)
    {

        int n = v.size();
        int m = v[0].size();

        if (i < 0 || j < 0 || i >= n || j >= m)
        {
            return;
        }

        vs[i][j] = true;
        q.push({0, {i, j}});

        if (i + 1 < n && !vs[i + 1][j] && v[i + 1][j] == 1)
        {
            dfs(i + 1, j, vs, v);
        }

        if (j + 1 < m && !vs[i][j + 1] && v[i][j + 1] == 1)
        {
            dfs(i, j + 1, vs, v);
        }

        if (i - 1 >= 0 && !vs[i - 1][j] && v[i - 1][j] == 1)
        {
            dfs(i - 1, j, vs, v);
        }

        if (j - 1 >= 0 && !vs[i][j - 1] && v[i][j - 1] == 1)
        {
            dfs(i, j - 1, vs, v);
        }

        return;
    }

    int bfs(queue<pair<int, pair<int, int>>> q, vector<vector<bool>> &vs, vector<vector<int>> &v)
    {

        int n = v.size();
        int m = v[0].size();

        while (!q.empty())
        {
            int d = q.front().first;
            int i = q.front().second.first;
            int j = q.front().second.second;
            q.pop();

            if (i + 1 < n && !vs[i + 1][j])
            {
                q.push({d + 1, {i + 1, j}});
                vs[i + 1][j] = true;
                if (v[i + 1][j] == 1)
                {
                    return d;
                }
            }

            if (j + 1 < m && !vs[i][j + 1])
            {
                q.push({d + 1, {i, j + 1}});
                vs[i][j + 1] = true;
                if (v[i][j + 1] == 1)
                {
                    return d;
                }
            }

            if (i - 1 >= 0 && !vs[i - 1][j])
            {
                q.push({d + 1, {i - 1, j}});
                vs[i - 1][j] = true;
                if (v[i - 1][j] == 1)
                {
                    return d;
                }
            }

            if (j - 1 >= 0 && !vs[i][j - 1])
            {
                q.push({d + 1, {i, j - 1}});
                vs[i][j - 1] = true;
                if (v[i][j - 1] == 1)
                {
                    return d;
                }
            }
        }

        return -1;
    }

    int shortestBridge(vector<vector<int>> &A)
    {

        int n = A.size();
        int m = A[0].size();

        vector<vector<bool>> vs(n, vector<bool>(m, false));

        for (int i = 0; i < A.size(); i++)
        {
            bool flag = false;
            for (int j = 0; j < A[0].size(); j++)
            {
                if (A[i][j] == 1)
                {
                    dfs(i, j, vs, A);
                    flag = true;
                    break;
                }
            }

            if (flag)
            {
                break;
            }
        }

        return bfs(q, vs, A);
    }
};
```