<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 {
    /*
    find the first 1 in the grid.
    do dfs on that one and hence get the first connected component
    consider all the 1's of the first connected component and do
    a multi source bfs to the next 1
    tc : o(n*n)
    */
public:
    void dfs(int i, int j,vector<vector<int>>& grid, set<pair<int,int>>& v )
    {
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || v.find({i,j})!=v.end() || grid[i][j]==0)
        {
            return;
        }

        v.insert({i,j});
        dfs(i-1,j,grid,v);
        dfs(i+1,j,grid,v);
        dfs(i,j-1,grid,v);
        dfs(i,j+1,grid,v);

    }
    int shortestBridge(vector<vector<int>>& grid) {
        set<pair<int,int>> v;
        int n = grid.size();
    
        for(int i=0;i<n;i++)
        {
            bool flag=false;
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    flag = true;
                    dfs(i,j,grid,v);
                    break;
                }

            }
            // break inside the inner loop will only break the inner loop
            // we also need to break the outer loop once we break the inner loop
            if(flag){break;}
        }

    
        // start multisource bfs from all the 1s in that first island
        // lets say if we decide to start bfs only from the last 1 in the first island
        // then it wont guarnatee us the shortest path or min number of 0 transitions.
        // because there is no way in DFS to get us the last 1 or there is nothing like that
        // so we have to check the shortest path from all 1s, whichever 1 reaches the other island 1
        // first, that apth will be our answer.
        queue<pair<int,int>> q;
        for(auto i : v)
        {
            q.push({i.first,i.second});
        }

        int ans=0;
        vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}};

        cout<<q.size();

        //we are using a visited set, so whenever if any neighbour is equal to 1
        // and it is visited that means it belongs to the is component or 1st
        // island. when the neighbor is equal to 0 then its fine, we can move
        // ahead accordingly, if visited then ignore, if not visited then add to queue.
        // so the only one left will be when the neighbor is 1 but it is not visited, that
        //is the 1 that belongs to the other island.
        // if we simply check for grid[nx][ny] equal to 1 right
                /*after we pop an element from the q, it would be wrong
                because the already makred 1's from the first connected 
                component are also 1, so every 1 that comes out
                of the queue is not necessarily the 1 we sre looking for
                there is one thing special about the 1 we are looking for
                it is, that when we are exploring any element and when we
                encounter a 1 , if it is not visited then that is the 1 
                we are looking for. but we have to do this while we are exploring
                usually we check right after we pop, but here we have to check while
                we are exploring. because if we check right after we pop, then that
                1 that we were looking for would have been visited.
                */
        while(!q.empty())
        {
            int size = q.size();
            while(size)
            {
               pair<int,int> cur = q.front();
               q.pop();

               int x = cur.first;
               int y = cur.second;

            //    if(grid[x][y]==1)
            //    {
            //     return ans;
            //    }

               // explore x,y
               for(vector<int>& dir : dirs)
               {
                  int n_x = x+dir[0];
                  int n_y = y+dir[1];

                  if(n_x>=0 && n_y>=0 && n_x<n && n_y<n)
                  {
                    if(v.find({n_x,n_y})!=v.end()) 
                    {
                        continue;
                    }
                    else
                    {
                        if(grid[n_x][n_y]==1)
                        {
                            /* we dont increment answer here because, we want number of zeros
                            that we need to convert. so suppose we have been through 2 levels
                            that is 2 zeros and hence answer now is 2, but in the current level
                            the moment we reach 1, we dont need to increase answer because the num
                            of zeros converted will be 2 only.
                            */
                            return ans;
                        }
                        v.insert({n_x,n_y});
                        q.push({n_x,n_y});
                    }
                  }
               }
              size--;

            }
            cout<<ans;
            ans++;
        }

        return -1;
        
    }
};
33715