bfs未过36分求助
查看原帖
bfs未过36分求助
593255
dist_22r楼主2022/10/27 19:36
#include<bits/stdc++.h>
using namespace std;
int h,t,num=0,s,n,dirx[4]={-1,0,1,0},diry[4]={0,1,0,-1},b[1001][1001];
char a[1001][1001],d[1001][1001];
struct cell{
	int x,y;
}c[1001];
void bfs(int dx,int dy)
{
	h=0;
	t=1;
	c[1].x=dx;
	c[1].y=dy;
	b[dx][dy]=0;
	while(h<t)
	{
		h++;
		for(int g=0;g<4;g++)
		{
			int nx=c[h].x+dirx[g];
			int ny=c[h].y+diry[g];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&b[nx][ny]!=0)
			{
				t++;
				c[t].x=nx;
				c[t].y=ny;
				b[nx][ny]=0;
			}
		}
	}
	num++;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]!='.')
				b[i][j]=1;
			else
				b[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(b[i][j]!=0)
			{
				bfs(i,j);
			}
		}
	}
	s=num;
	num=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]=='.'||a[i+1][j]=='.'||a[i][j+1]=='.'||a[i-1][j]=='.'||a[i][j-1]=='.')
			{
				d[i][j]='.';
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=d[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[i][j]!='.')
				b[i][j]=1;
			else
				b[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(b[i][j]!=0)
			{
				bfs(i,j);
			}
		}
	}
	cout<<s-num<<endl;
	return 0;
}
2022/10/27 19:36
加载中...