1233. 全球变暖（bfs宽搜相邻点）

题目：

1233. 全球变暖 - AcWing题库

?

思路：bfs?

1.临接问题，最短路径问题--->bfs。

2.被完全淹没--->岛屿所以部分均临海。?

代码：?

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct Point
{
    int x,y;
};
queue<Point>q;
bool st[N][N];
char p[N][N];
int n;
int cnt;

//标记该岛屿的所以部分并判断是否所以部分均临海
void bfs(int px,int py,int &total,int &bound)
{
    st[px][py]=true;
    Point Start={px,py};
    q.push(Start);
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(q.size()){
        total++;
        Point t=q.front();
        q.pop();
        bool is_bound=false;//默认该坐标不邻海
        for(int i=0;i<4;i++){
            int x=t.x+dx[i],y=t.y+dy[i];
            if(x<0||x>=n||y<0||y>=n)continue;//越界
            if(st[x][y])continue;//重复
            if(p[x][y]=='.'){is_bound=true;continue;}//是海
            
            q.push({x,y});
            st[x][y]=true;//标记，避免回头杀
        }
        if(is_bound)bound++;//该坐标临海，会被淹没
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)scanf("%s",&p[i]);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!st[i][j]&&p[i][j]=='#')//是一块未被标记的岛屿
            {
                int total=0,bound=0;//分别表示该岛屿包含几个部分且有多少是临海的
                bfs(i,j,total,bound);//标记该岛屿的所以部分并判断是否所以部分均临海
                if(total==bound)cnt++;//该岛屿所以部分均临海---会被完全淹没
            }
        }
    }
    cout<<cnt;
}

?