<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 Node {
public: 
    int row;
    int col;
    int dist; 
    Node(int _row, int _col, int _dist){
        row = _row;
        col = _col;
        dist = _dist;
    }
};

class Solution {
public:
    vector<vector<int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    bool validMove(int row, int col, int rows, int cols){
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }

    void traverseIsland(int row, int col, vector<vector<int>>& grid, vector<vector<bool>>& visited, queue<Node*>& queue){
        visited[row][col] = true;
        queue.push(new Node(row, col, 0));

        for (auto currDirection: directions){
            int currRow = row + currDirection[0], currCol = col + currDirection[1];
            if (validMove(currRow, currCol, grid.size(), grid[0].size()) && visited[currRow][currCol] == false && grid[currRow][currCol] == 1){
                traverseIsland(currRow, currCol, grid, visited, queue);
            }
        }
    }

    int shortestBridge(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        queue<Node*> queue; // <row, col>
        
        for (int row = 0; row < rows; row++){
            bool found = false;
            for (int col = 0; col < cols; col++){
                if (grid[row][col] == 1){
                    traverseIsland(row, col, grid, visited, queue);
                    found = true;
                    break;
                }
            }
            if (found){
                break;
            }
        }


        while (!queue.empty()){
            int row = queue.front()->row;
            int col = queue.front()->col;
            int dist = queue.front()->dist;
            queue.pop();

            for (auto currDirection: directions){
                int currRow = row + currDirection[0];
                int currCol = col + currDirection[1];
                if (validMove(currRow, currCol, rows, cols) && visited[currRow][currCol] == false){
                    if (grid[currRow][currCol] == 1 && visited[currRow][currCol] == false){
                        return dist;
                    }
                    visited[currRow][currCol] = true;
                    queue.push(new Node(currRow, currCol, dist+1));
                }
            }
        }
        return -1;
    }
};
43915