<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 dfs(int i, int j, int count, vector<vector<int>>&grid){
        grid[i][j]=count;
        vector<int> x = {0, 0, 1, -1};
        vector<int> y = {1, -1, 0, 0};
        for(int k=0; k<4; ++k){
                if(i+x[k]>=grid.size() || j+y[k]>=grid[0].size() || i+x[k]<0 || j+y[k]<0 || grid[i+x[k]][j+y[k]]!=1)continue; 
                dfs(i+x[k], j+y[k], count, grid);    
        }
    }
    bool isOnEdge(vector<vector<int>> &grid, int i, int j){
        vector<int> x = {0, 0, 1, -1};
        vector<int> y = {1, -1, 0, 0};
        for(int k=0; k<4; ++k){
                if(i+x[k]>=grid.size() || j+y[k]>=grid[0].size() || i+x[k]<0 || j+y[k]<0 || grid[i+x[k]][j+y[k]]!=0)continue; 
                return true;   
        }
        return false;
    }
    int findShortestDistance(vector<vector<int>>& grid){
        queue<pair<pair<int, int>, int>>q;
        for(int i=0; i<grid.size(); ++i){
            for(int j=0; j<grid[0].size(); ++j){
                if(grid[i][j]==2 && isOnEdge(grid, i, j))q.push({{i, j}, 0});
            }
        }
        int n= grid.size();
        int m = grid[0].size();
        cout << n << "  " << m << endl;
        // cout << grid[2][2] << endl;
        while(!q.empty()){
            pair<pair<int, int>, int> top = q.front();
            q.pop();
            int i = top.first.first;
            int j = top.first.second;
            int dist = top.second;
            cout << i << " " << j << " " << dist << endl;
            if(grid[i][j]==3)return dist-1;
            // grid[i][j]=2;
            if(i+1<n && grid[i+1][j]!=2){
                if(grid[i+1][j]==3) return dist;
                grid[i+1][j] = 2;
                q.push({{i+1, j}, dist+1});
            }
            if(j+1<m && grid[i][j+1]!=2){
                if(grid[i][j+1]==3) return dist;
                grid[i][j+1] = 2;
                q.push({{i, j+1}, dist+1});
            }
            if(i-1>=0 && grid[i-1][j]!=2){
                if(grid[i-1][j]==3) return dist;
                grid[i-1][j] = 2;
                q.push({{i-1, j}, dist+1});
            }
            if(j-1>=0 && grid[i][j-1]!=2){
                if(grid[i][j-1]==3) return dist;
                grid[i][j-1] = 2;
                q.push({{i, j-1}, dist+1});
            }
            
        }
        return -1;
    }
    int shortestBridge(vector<vector<int>>& grid) {
        int count = 2;
        for(int i=0; i<grid.size(); ++i){
            for(int j=0; j<grid[0].size(); ++j){
                if(grid[i][j]==1){
                    dfs(i, j, count, grid);
                    count++;
                }
            }
        }
        for(int i=0; i<grid.size(); ++i){
            for(int j=0; j<grid[0].size(); ++j){
                cout<<grid[i][j]<<" ";
            }
            cout<<endl;
        }
        // return 0;
        return findShortestDistance(grid);
    }
};
32185