class Solution {
    constexpr static int direction[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
public:
    int shortestBridge(vector<vector<int>>& grid) {
        //计算数组长宽，使用mark标记岛屿格子
        int m = grid.size(), n = grid[0].size(), mark = 2;
        queue<pair<int, int>> q;//用于BFS的队列

        function<void(int, int)> dfs = [&](int i, int j) {//dfs函数
            grid[i][j] = mark;//每遍历一个格子，标记之，防止重复遍历
            
            bool isBorder = false;
            //用于标记格子是否在岛屿边界，
            //如果在岛屿边界入队用于后续BFS求两岛间距
            
            for (const auto& [iOfs, jOfs] : direction) {//依次dfs四个方向上的陆地格子
                int x = i + iOfs, y = j + jOfs;//邻居格子坐标
                if (x >= 0 and x < m and y >= 0 and y < n) {//坐标合法性判断
                    if (grid[x][y] == 1) dfs(x, y);//如果邻居格子值为1，dfs之
                    else if (grid[x][y] == 0) isBorder = true;//否则本格子是岛屿边界
                }
            }
            if (isBorder) q.emplace(make_pair(i, j));//如果本格子是岛屿边界，入队之
        };
        for (int k = 0; k < m; ++k) {//dfs第一个岛屿并入队其边界格子
            for (int z = 0; z < n; ++z) {
                if (grid[k][z] == 1) {
                    dfs(k, z);
                    ++mark;
                    break;
                }
            }
            if (mark == 3) break;
        }
        //存答案，以及bfs需要用到的队列大小，当前格子计数
        int ans = 0, size = q.size(), count = 0;
        while (!q.empty()) {//当队列非空，bfs扩展边界直至与另一个岛屿接触
            auto& [i, j] = q.front();//获取队头格子坐标
            q.pop();//将其出队
            if (ans >= 5) cout << 'a' << " ";//断点a
            //向格子四周拓展边界
            for (const auto& [iOfs, jOfs] : direction) {
                if (ans >= 5) cout << 'b' << " ";//断点b
                int x = i + iOfs, y = j + jOfs;

                if (ans >= 5) cout << 'c' << " ";//断点c
                if (x >= 0 and x < m and y >= 0 and y < n) {
                    if (ans >= 5) cout << 'd' << " ";//断点d
                    if (grid[x][y] == 1) return ans;
                    else if (grid[x][y] == 0) {
                        if (ans >= 5) cout << 'e' << " ";//断点e
                        grid[x][y] = mark;
                        if (ans >= 5) cout << 'f' << " ";//断点f
                        q.emplace(make_pair(x, y));
                    }
                }
            }
            ++count;//记录当前边界已拓展节点数量
            if (count == size) {//如果当前边界已拓展完毕
                size = q.size();//更新新边界节点数量
                count = 0;//初始化计数器
                ++ans;//两岛屿间距加一
            }
            cout << ans << " ";//断点g兼ans值监视
        }
        return ans;//返回答案
    }
};

 vector<vector<int>> v = {
        {1,0,1,1,0,0,0,0,0,0},
        {1,1,1,1,1,1,0,0,0,0},
        {0,1,1,0,1,1,0,0,0,0},
        {0,0,1,1,0,0,0,0,0,0},
        {0,0,1,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,1},
        {0,0,0,0,0,0,0,1,1,1},
        {0,0,0,0,0,0,1,1,1,1},
        {0,0,0,0,0,1,1,1,1,1}
    };