<p>You are given an <code>n x n</code> binary matrix <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water.</p>

<p>An <strong>island</strong> is a 4-directionally connected group of <code>1</code>&#39;s not connected to any other <code>1</code>&#39;s. There are <strong>exactly two islands</strong> in <code>grid</code>.</p>

<p>You may change <code>0</code>&#39;s to <code>1</code>&#39;s to connect the two islands to form <strong>one island</strong>.</p>

<p>Return <em>the smallest number of </em><code>0</code><em>&#39;s you must flip to connect the two islands</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[0,1],[1,0]]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[0,1,0],[0,0,0],[0,0,1]]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> 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]]
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length == grid[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
	<li>There are exactly two islands in <code>grid</code>.</li>
</ul>

class Solution {
public:

    
    void bfs(queue<vector<int>> q, vector<vector<int>> &arr){
        vector<vector<int>> dir = {{0,1},{0,-1},{-1,0},{1,0}};
        int n = arr.size();
        int m = arr[0].size();

        while(q.size()!=0){
            vector<int> a = q.front();
            q.pop();
            int i = a[0];
            int j = a[1];

            for(int k=0; k<4; k++){
                int nr = i+dir[k][0];
                int nc = j+dir[k][1];

                if(nr>=0 && nc>=0 && nr<n && nc<m && arr[nr][nc]==1){
                    arr[nr][nc]=-1;
                    q.push({nr,nc});
                }
            }
        }
    }

    int bfs2(queue<vector<int>> q, vector<vector<int>> &arr, vector<vector<int>> visited){
        vector<vector<int>> dir = {{0,1},{0,-1},{-1,0},{1,0}};
        int n = arr.size();
        int m = arr[0].size();

        while(q.size()!=0){
            vector<int> a = q.front();
            q.pop();
            int i = a[0];
            int j = a[1];
            int step = a[2];
            visited[i][j] = 1;
            for(int k=0; k<4; k++){
                int nr = i+dir[k][0];
                int nc = j+dir[k][1];
                if(nr>=0 && nc>=0 && nr<n && nc<m && visited[nr][nc]==0){

                    if(arr[nr][nc]==-1){
                        return step;
                    }else{
                        visited[nr][nc] = 1;
                        q.push({nr,nc,step+1});
                    }
                }
            }
        }
        return -1;
    }


    int shortestBridge(vector<vector<int>>& arr) {
        int n = arr.size();
        int m = arr[0].size();

        queue<vector<int>> q;
        vector<int> a;

        for(int i=0; i<n; i++){
            int count = 0;
            for(int j=0; j<m; j++){
                if(arr[i][j]==1){
                   a = {i,j};
                   break;
                }
            }
        }

        arr[a[0]][a[1]] = -1;
        q.push(a);
        bfs(q,arr);
        

        queue<vector<int>> qu;
        for(int i=0; i<n; i++){
            int count = 0;
            for(int j=0; j<m; j++){
                if(arr[i][j]==1){
                   qu.push({i,j,0});
                }
            }
        }

        vector<vector<int>> visited(n,vector<int>(m,0));

        return bfs2(qu,arr,visited);
        //return ans;
    }
};
44425