題目描述

給你一個大小為?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;}
};