day66—BFS—最短的桥（LeetCode-934）

题目描述

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

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

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

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

输入格式

一个二维整数数组，输出是一个非负整数，表示需要填海造陆的位置数。
Input:
[[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：

输入：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 中恰有两个岛

解决方案：

1、递归广度搜索部分：

终止条件：识别 0 则加入到队列中

单层递归：从该点的四个方向开始，一圈一圈的散射式搜索展开

2、主函数判断部分：

递归加入条件：遍历到 1 即加入循环判断周围有无 0

设置可变条件：bool filpped：是否可翻转

3、答案计数部分：

对于每层的循环加入的 0 位置点，周围是否存在 1 位置点可达并记录。

函数源码：

class Solution {
public:

    void bfs(queue<pair<int,int>>& points,vector<vector<int>>&grid,int row,int col,int i,int j){

        //越界条件判断
        if( i<0 || j<0 || i==row || j==col || grid[i][j]==2 )   return;

        //找到并记录 0 点位置
        if(grid[i][j]==0){
            points.push({i,j});
            return;
        }

        //降重，防止重复遍历
        grid[i][j]=2;
        
        //从该点的四个方向开始，一圈一圈的散射式搜索展开
        bfs(points,grid,row,col,i-1,j);
        bfs(points,grid,row,col,i+1,j);
        bfs(points,grid,row,col,i,j-1);
        bfs(points,grid,row,col,i,j+1);

    }

//-------------------------------------------------------
    vector<int> direction{-1,0,1,0,-1};
    int shortestBridge(vector<vector<int>>& grid) {
        int row=grid.size();
        int col=grid[0].size();

        queue<pair<int,int>> points;

        bool flipped = false;   //flipped: 翻转
        for(int i=0;i<row;i++){
            if(flipped) break;
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    bfs(points,grid,row,col,i,j);
                    flipped=true;
                    break;
                }
               
            }

        }
//-------------------------------------------------------
        int x,y;
        int level=0;

        while(!points.empty()){
            level++;
            int n_points=points.size();
            while(n_points--){
                auto[r,c]=points.front();
                points.pop();
                for(int k=0;k<4;k++){
                    x=r+direction[k];
                    y=c+direction[k+1];
                    if(x>=0 && y>=0 && x<row && y<col){
                        if(grid[x][y]==2)   continue;
                        if(grid[x][y]==1)   return level;

                        points.push({x,y});
                        grid[x][y]=2;
                    }
                }


            }
        
        }

        return 0;
    }
};