[数据结构与算法]LeetCode每日一题：934. 最短的桥（中等） bfs dfs

题目：

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。

岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。

你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。

返回必须翻转的 0 的最小数目。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：1
示例 2：

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2
示例 3：

输入：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]]
输出：1
?

提示：

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] 为 0 或 1
grid 中恰有两个岛

先找出一个岛，将其重新赋值，与0和1区别开，用dfs就可以找，将找到的第一个岛放到队列中。将第一个岛的点做bfs，每做一轮答案增加一个，知道找到第二个岛结束。

class Solution {
public:
    int  n;
    int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    queue<pair<int ,int > > que ;

    void dfs(int x , int y , vector<vector<int>>& grid){
        if(grid[x][y] != 1) return ;
        grid[x][y]=2;
         que.push({x,y});
        for(int i = 0 ; i < 4 ; i++ ){
            int nx = x + d[i][0] , ny = y + d[i][1] ;
            if(nx >= 0 && nx < n && ny >= 0 && ny < n )
                dfs(nx , ny ,grid);
        }
    }
    void search(vector<vector<int>>& grid){ //先找到第一个岛的一个点再开始深度遍历
        for(int i = 0 ; i < n ; i ++ )
            for(int j = 0 ; j < n ; j ++ )
                if(grid[i][j]) {
                    dfs(i,j,grid);
                    return ;
                }
    }


    int bfs(vector<vector<int>>& grid){
        int ans = 0 ;
        while (!que.empty()) {
            for (int m = que.size() ; m ; m--) {
                auto [x, y] = que.front();
                que.pop();
                for (int k = 0; k < 4; ++k) {
                    int nx = x + d[k][0], ny = y + d[k][1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        if (grid[nx][ny] == 1) return ans;
                        if (grid[nx][ny] == 0) {
                            grid[nx][ny] = 2;
                            que.push({nx,ny});
                        }
                    }
                }
            }//一轮结束，层数增加
            ++ans;
        }
        return ans ;
    }
    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size() ;
        search(grid);
        return bfs(grid);
    }
};