934

class Solution {
public:
    int n, m;
    int dir[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
    int shortestBridge(vector<vector<int>>& A) {
        n=A.size(); m =A[0].size();

        // Flood fill one island.
        bool found = false;
        for(int i=0; i<n && !found; i++)
            for(int j=0; j<m && !found; j++)
                if(A[i][j]){
                    found = true;
                    fill(A, i, j, 2);
                }

        // BFS on border cells.
        queue<pair<int, int>> q;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(A[i][j] == 2)
                    q.push({i, j});

        int steps = 0;
        while(!q.empty()){
            int sz = q.size();
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                int x = p.first, y = p.second;
                for(int j=0; j<4; j++){
                    int nextX = x+dir[j][0], nextY = y+dir[j][1];
                    if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || A[nextX][nextY] == 2) continue;
                    if(A[nextX][nextY] == 1) return steps;
                    A[nextX][nextY] = 2;
                    q.push({nextX, nextY});
                }
            }
            steps++;
        }
        return steps;
    }

    void fill(vector<vector<int>>& A, int x, int y, int col){
        A[x][y] = col;
        for(int i=0; i<4; i++){
            int nextX = x+dir[i][0], nextY = y+dir[i][1];
            if(nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || A[nextX][nextY] != 1 || A[nextX][nextY] == 0) continue;
            fill(A, nextX, nextY, col);
        }
    }

};