<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:
    int m;
    int n;
    vector <vector<int> > directions ={
             {-1,0},
     {0,-1} ,        {0, 1},
             {1,0} 
    
    };
    bool isSafe(int i, int j)
    {
    if(i>=0 and i< m and  j>=0 and  j<n) return true;
    return false; 

    }



    void dfs(vector<vector<int>> &grid , int i, int j ,   set<pair<int , int>> &visitedCell)
    {
    if( !isSafe(i,j) || grid[i][j] ==0 || visitedCell.find({i,j}) != visitedCell.end())
    return;

    visitedCell.insert({i,j});  // i,j se kha kha jaa sakte hai

    for(auto x : directions)   
    {
        int i_ = i + x[0];
        int j_ = j + x[1];

        dfs(grid, i_, j_, visitedCell);
    }

    }



    int bfs(vector<vector<int>> &grid ,  set<pair<int , int>> &visitedCell)

    {

    queue<pair<int , int>> que;
    for(auto x : visitedCell)
    que.push(x);

    int level = 0;

    while(!que.empty())
    {
        int L = que.size();
        while(L--)
        {
      pair<int , int> p =que.front();
      que.pop();
      

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

      for(auto dir : directions){
      int x_ = x + dir[0];
      int y_ = y + dir[1];  
      
      if(isSafe(x_,y_) && visitedCell.find({x_,y_}) == visitedCell.end())
      {
       
       if(grid[x_][y_] == 1)
       {
        return level;
       }

       visitedCell.insert({x_, y_});
       que.push({x_, y_});

      }
      }
      
      

        }
        level++;
    }
return level;

    }
    
    
    int shortestBridge(vector<vector<int>>& grid) {
      m = grid.size();
      n = grid[0].size();
      set<pair<int , int>>visitedCell;
      for(int i=0; i<m; i++)
      {
        for(int j=0; j<n; j++){  
        
        if(grid[i][j] ==1){  // found 1st island
        dfs(grid , i , j , visitedCell);  // mark all 1 cell of visited island and store them in visted island
        return bfs(grid , visitedCell);
      }  
      }
    }
return -1;

    }
};
46465