蒟蒻 90 pts WA #2 求调
查看原帖
蒟蒻 90 pts WA #2 求调
352913
123xiayicheng楼主2023/4/13 21:09

#include<bits/stdc++.h>
using namespace std;
int ma[4010][4010],n1,m1,n2,m2,nn=2002,nm=2002;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int cnt=0;
void print()
{
	for(int i=n1-2;i<=n2+2;i++)
	{
		for(int j=m1-2;j<=m2+2;j++)
		{
			printf("%d ",ma[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
void bfs(int i,int j)
{
	queue <pair<int,int> > q;
	ma[i][j]=1;
	q.push({i,j});
	while(!q.empty())
	{
		//              print();
		int tx=q.front().first,ty=q.front().second;
		//      cout<<tx<<" "<<ty<<endl;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=tx+dx[i];
			int ny=ty+dy[i];
			if(nx>=n1-2 and nx<=n2+2 and ny>=m1-2 and ny<=m2+2 and !ma[nx][ny])
			{
				q.push({nx,ny});
				ma[nx][ny]=1;
			}
		}
	}
}
int main(){
	int T;
	cin>>T;
	n1=n2=2002,m1=m2=2002;
	ma[n1][m1]=1;
	while(T--)
	{
		char c;
		scanf("%c",&c);
		if(c=='N')
			nn-=2,n1=min(n1,nn),ma[nn][nm]=1,ma[nn+1][nm]=1;
		if(c=='S')
			nn+=2,n2=max(nn,n2),ma[nn][nm]=1,ma[nn-1][nm]=1;
		if(c=='E')
			nm+=2,m2=max(m2,nm),ma[nn][nm]=1,ma[nn][nm-1]=1;
		if(c=='W')
			nm-=2,m1=min(m1,nm),ma[nn][nm]=1,ma[nn][nm+1]=1;
	}
	//  cout<<n1<<" "<<m1<<" "<<n2<<" "<<m2<<" "<<nn<<" "<<nm<<endl;
	for(int i=n1-2;i<=n2+2;i++)
	{
		for(int j=m1-2;j<=m2+2;j++)
		{
			if(!ma[i][j])
			{
				cnt++,
				bfs(i,j);
			}
		}
	}
	cout<<cnt-1;
	return 0;
}
2023/4/13 21:09
加载中...