<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<pair<int,int>>& q,vector<vector<int>>& a,vector<vector<int>>& vis){
    int x,y,n=(int)vis.size();

    while(!q.empty()){
        x=q.front().first;
        y=q.front().second;
        q.pop();

        if(x-1>-1 && a[x-1][y] && !vis[x-1][y]) {vis[x-1][y]=1;q.push({x-1,y});}
        if(x+1<n && a[x+1][y] && !vis[x+1][y]) {vis[x+1][y]=1;q.push({x+1,y});}
        if(y-1>-1 && a[x][y-1] && !vis[x][y-1]) {vis[x][y-1]=1;q.push({x,y-1});}
        if(y+1<n && a[x][y+1] && !vis[x][y+1]) {vis[x][y+1]=1; q.push({x,y+1});}
    }
}

void bfs2 (queue<pair<int,int>>& q,vector<vector<int>>& a,vector<vector<int>>& vis,vector<vector<int>>& dist){
    int x,y,n=(int)vis.size();

    while(!q.empty()){
        x=q.front().first;
        y=q.front().second;
        q.pop();

        if(x-1>-1 && !a[x-1][y] && !vis[x-1][y]) {vis[x-1][y]=1;dist[x-1][y]=dist[x][y]+1;q.push({x-1,y});}
        if(x+1<n && !a[x+1][y] && !vis[x+1][y]) {vis[x+1][y]=1;dist[x+1][y]=dist[x][y]+1; q.push({x+1,y});}
        if(y-1>-1 && !a[x][y-1] && !vis[x][y-1]) {vis[x][y-1]=1;dist[x][y-1]=dist[x][y]+1;q.push({x,y-1});}
        if(y+1<n && !a[x][y+1] && !vis[x][y+1]) {vis[x][y+1]=1;dist[x][y+1]=dist[x][y]+1; q.push({x,y+1});}
    }
}

    int shortestBridge(vector<vector<int>>& a) {
        int i,j,k,n=(int)a.size(),strow,stcol,mn,md=1000000007;
        vector<vector<int>> vis,loc,dist[2];
        queue<pair<int,int>> qu;

        vis.resize(n);
        loc.resize(n);
        for(i=0;i<n;i++) {vis[i].resize(n);loc[i].resize(n);}

        for(i=0;i<2;i++){
            dist[i].resize(n);
            for(j=0;j<n;j++) dist[i][j].resize(n);
        }

        for(i=0;i<n;i++){
            for(j=0;j<n;j++)
            if(a[i][j]==1) break;
            if(j!=n) break;
        }

        strow=i;
        stcol=j;
        vis[i][j]=1;
        qu.push({i,j});
        bfs(qu,a,vis);

        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(vis[i][j]) {loc[i][j]=1;vis[i][j]=0;}

        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(a[i][j] && !loc[i][j]) break;
            }
            if(j!=n) break;
        }
        strow=i;stcol=j;
        vis[i][j]=1;
        qu.push({i,j});
        bfs(qu,a,vis);

        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(vis[i][j]) {loc[i][j]=2;vis[i][j]=0;}

        for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if(loc[i][j]==1) {vis[i][j]=1;qu.push({i,j});}
            if(a[i][j]==0) dist[0][i][j]=md;
        }
        
        bfs2(qu,a,vis,dist[0]);

        for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            vis[i][j]=0;
            if(loc[i][j]==2) {vis[i][j]=1;qu.push({i,j});}
            if(a[i][j]==0) dist[1][i][j]=md;
        }

        bfs2(qu,a,vis,dist[1]);

        mn=md;
        for(i=0;i<2;i++){
            for(j=0;j<n;j++){
                for(k=0;k<n;k++){
                    if(a[j][k]==0){
                        mn=min(mn,dist[0][j][k]+dist[1][j][k]-1);
                    }
                }
            }
        }

        return mn;

    }
};
31675