LeetCode 934.最短的桥

LeetCode 934.最短的桥

题目限制了岛的数量肯定为2，所以我们只需要找到两个岛即可，首先通过遍历每一个坐标找到一个岛的点（值为1），接着以这个点开始DFS，找到该岛上所有的点，并将值设为-1，然后以这些点为基础集合，再进行BFS，当找到第一个值为1的点时，BFS的层数就是需要翻转的数目

class Solution {
public:
    void dfs(int x,int y, vector<vector<int>>& grid, queue<pair<int, int>> &qu){
        if(x<0 || y<0 || x>=grid.size() || y>=grid[0].size() || grid[x][y]!=1)  return;
        qu.emplace(x, y);
        grid[x][y]=-1;
        dfs(x-1, y, grid, qu);
        dfs(x+1, y, grid, qu);
        dfs(x, y-1, grid, qu);
        dfs(x, y+1, grid, qu);
    }
    int shortestBridge(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dir={{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1)
                {
                    queue<pair<int, int>> qu;
                    dfs(i, j, grid, qu);
                    int step=0;
                    while(!qu.empty()){
                        int sz=qu.size();
                        for(int i=0;i<sz;i++)
                        {
                            auto [x, y] = qu.front();
                            qu.pop();
                            for(int k=0;k<4;k++)
                            {
                                int nx= x + dir[k][0];
                                int ny=y+dir[k][1];
                                if(nx>=0 && ny>=0 && nx<n && ny<n){
                                    if(grid[nx][ny]==0){
                                        qu.emplace(nx, ny);
                                        grid[nx][ny] = -1;
                                    }
                                    else if(grid[nx][ny]==1){
                                        return step;
                                    }
                                }
                            }
                        }
                        step++;
                    }
                }
            }
        }
        return 0;
    }
};