24pts求条
查看原帖
24pts求条
1033649
wsljh楼主2024/7/26 16:07
#include<bits/stdc++.h>
using namespace std;
int n,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},cnt,ans;
char a[1010][1010];
struct node
{
    int x,y;
}q[1010*1010];
void bfs(int x1,int y1)
{
    int head=1,tail=1;
    q[tail].x=x1;
    q[tail].y=y1;
    tail++;
    while(head<tail)
    {
        int x=q[head].x;
        int y=q[head].y;
        a[x][y]='%';
        for(int i=0;i<4;i++)
        {
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(0<nx&&nx<=n&&0<ny&&ny<=n&&a[nx][ny]=='#')
            {
                q[tail].x=nx;
                q[tail].y=ny;
                tail++;
            }
        }
        head++;
    }
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='#')
			{
				cnt++;
				bfs(i,j);
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='.')
			{
				if(a[i-1][j]=='%')a[i-1][j]='&';
				if(a[i+1][j]=='%')a[i+1][j]='&';
				if(a[i][j+1]=='%')a[i][j+1]='&';
				if(a[i][j-1]=='%')a[i][j-1]='&';
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]=='%')a[i][j]='#';
			if(a[i][j]=='&')a[i][j]='.';
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(a[i][j]=='#')
			{
				ans++;
				bfs(i,j);
			}
	cout<<cnt-ans;	
	return 0;
}
2024/7/26 16:07
加载中...