AcWing 1233. 全球变暖 k=4终极无敌拽炸天的想法,仅此一家
原题链接
简单
#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N=1010;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
typedef pair<int,int>pii;
bool mark[N][N];
//bool flag;
char map[N][N];
int n,m,ans,totle;
void bfs(int x,int y)
{
totle++;
mark[x][y]=true;
queue<pii>q;
q.push({x,y});
bool flag=false;
while(!q.empty())
{
int k=0;
pii top=q.front();
for(int i=0;i<4;i++)
{
int nex=top.x+dx[i];
int ney=top.y+dy[i];
if(nex<0||nex>=n||ney<0||ney>=n||map[nex][ney]=='.')
continue;
k++;
if(k==4&&flag==false) ans++,flag=true; ///如果满足条件,说明这个点的东南西北都是陆地,不会淹没
if(mark[nex][ney]==true)
continue;
q.push({nex,ney}); ///continue语句,执行continue。则无法运行到下面的语句,因此也不会插入队列中
mark[nex][ney]=true;
}
q.pop(); ////删除队列最开始的点位
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%s",&map[i]);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
if(map[i][j]=='#'&&mark[i][j]==false)
{
bfs(i,j);
}
}
cout<<totle-ans<<endl;
return 0;
}