You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

&nbsp;
Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1


Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2


Example 3:

Input: 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]]
Output: 1


&nbsp;
Constraints:


	n == grid.length == grid[i].length
	2 &lt;= n &lt;= 100
	grid[i][j] is either 0 or 1.
	There are exactly two islands in grid.


class Solution:
    def shortestBridge(self, grid):
        m, n = len(grid), len(grid[0])
        start_i, start_j = next((i, j) for i in range(m) for j in range(n) if grid[i][j])
        
        
        stack = [(start_i, start_j)]
        visited = set(stack)
        while stack:
            i, j = stack.pop()
            visited.add((i, j))  
            for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
                if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] and (ii, jj) not in visited:
                    stack.append((ii, jj))
                    visited.add((ii, jj))
        
        
        ans = 0
        queue = list(visited)
        while queue:
            new_queue = []
            for i, j in queue:
                for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
                    if 0 <= ii < m and 0 <= jj < n and (ii, jj) not in visited:
                        if grid[ii][jj] == 1:
                            return ans
                        new_queue.append((ii, jj))
                        visited.add((ii, jj))
            queue = new_queue
            ans += 1
class Solution {
    private static int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
    public int shortestBridge(int[][] grid) {
        boolean[][] visited=new boolean[grid.length][grid[0].length];
        LinkedList<Pair> queue=new LinkedList<Pair>();
        boolean found=false;
        for(int i=0;i<grid.length && !found;i++){
            for(int j=0;j<grid[0].length && !found;j++){
                if(grid[i][j]==1){
                    dfs(grid,i,j,queue,visited);
                    found=true;
                }
            }
        }
        int level=0;
        while(queue.size()>0){
            int size=queue.size();
            while(size-- >0){
                Pair pair=queue.poll();
                for(int k=0;k<4;k++){
                    int rowDash=pair.row+dirs[k][0];
                    int colDash=pair.col+dirs[k][1];
                    if(rowDash<0 || colDash<0 || rowDash>=grid.length || colDash>=grid[0].length ||
                       visited[rowDash][colDash]==true )continue;
                    if(grid[rowDash][colDash]==1) return level;
                    queue.add(new Pair(rowDash,colDash));
                    visited[rowDash][colDash]=true;
                }
            }
            level++;
        }
        return -1;
    }
    private void dfs(int[][] grid,int i,int j,LinkedList<Pair> queue,boolean[][] visited){
        visited[i][j]=true;
        queue.add(new Pair(i,j));
        for(int k=0;k<4;k++){
            int rowDash=i+dirs[k][0];
            int colDash=j+dirs[k][1];
        if(rowDash<0 || colDash<0 || rowDash>=grid.length || colDash>=grid[0].length ||
           visited[rowDash][colDash]==true || grid[rowDash][colDash]==0)continue;
        dfs(grid,rowDash,colDash,queue,visited);
        }
    }
    static class Pair{
        int row;
        int col;
        public Pair(int row,int col){
            this.row=row;
            this.col=col;
        }
    }
}
class Solution {
public:
    void findOneIsland(vector<vector<int>>& grid, int i, int j, queue<pair<int, int>>& q){
        if(i<0 || j<0 || i==grid.size() || j==grid.size() || grid[i][j]!=1)
            return;
        grid[i][j] = 2;
        q.push({i,j});

        findOneIsland(grid, i, j-1, q);
        findOneIsland(grid, i, j+1, q);
        findOneIsland(grid, i-1, j, q);
        findOneIsland(grid, i+1, j, q);

    }
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> q;
        int res=0;
        bool OneIslandFound = false;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    OneIslandFound = true;
                    findOneIsland(grid, i, j, q);
                    break;
                }
            }
            if(OneIslandFound)
                break;
        }

        while(!q.empty()){
            int i=q.front().first, j=q.front().second;
            q.pop();
            if(i!=0 && grid[i-1][j]<2){
                if(grid[i-1][j]==1){
                    res = grid[i][j]-2;
                    break;
                }
                if(grid[i-1][j]==0){
                    grid[i-1][j] = grid[i][j]+1;
                    q.push({i-1, j});
                }
            }

            if(i!=grid.size()-1 && grid[i+1][j]<2){
                if(grid[i+1][j]==1){
                    res = grid[i][j]-2;
                    break;
                }
                if(grid[i+1][j]==0){
                    grid[i+1][j] = grid[i][j]+1;
                    q.push({i+1, j});
                }
            }

            if(j!=0 && grid[i][j-1]<2){
                if(grid[i][j-1]==1){
                    res = grid[i][j]-2;
                    break;
                }
                if(grid[i][j-1]==0){
                    grid[i][j-1] = grid[i][j]+1;
                    q.push({i, j-1});
                }
            }

            if(j!=grid.size()-1 && grid[i][j+1]<2){
                if(grid[i][j+1]==1){
                    res = grid[i][j]-2;
                    break;
                }
                if(grid[i][j+1]==0){
                    grid[i][j+1] = grid[i][j]+1;
                    q.push({i, j+1});
                }
            }
        }
        return res;
    }
};
/**
 * @param {number[][]} grid
 * @return {number}
 */
const DIR = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0]
];

var shortestBridge = function(grid) {
    const que = [];
    const ROWS = grid.length;
    const COLS = grid[0].length;

    // find first insland
    outer:
    for(let row=0; row<ROWS; row++) {
        for(let col=0; col<COLS; col++) {
            if(grid[row][col] == 1) {
                const stack = [[row, col]];
                while(stack.length) {
                    const [r, c] = stack.pop();
                    que.push([r, c]);
                    grid[r][c] = 2; // mark as visited.
                    for(const dir of DIR) {
                        const newRow = r+dir[0];
                        const newCol = c+dir[1];
                        if(newRow<0 || newCol<0 || newRow>=ROWS || newCol>=COLS) continue;
                        if(grid[newRow][newCol] != 1) continue;
                        stack.push([newRow, newCol]);
                    }
                }
                break outer;
            }
        }
    }
    let steps = 0;
    while(que.length) {
        let size = que.length;
        for(let i=0; i<size; i++) {
            const [row, col] = que.shift();
            for(const dir of DIR) {
                const newRow = row+dir[0];
                const newCol = col+dir[1];
                if(newRow<0 || newCol<0 || newRow>=ROWS || newCol>=COLS) continue;
                if(grid[newRow][newCol] == 2) continue;
                if(grid[newRow][newCol] == 1) return steps;
                grid[newRow][newCol] = 2; // mark as visited.
                que.push([newRow, newCol]);
            }
        }
        steps++;
    }
    return -1;
};
Shortest Bridge