TLE46分求助
查看原帖
TLE46分求助
1255953
Qianyihan1221楼主2024/12/5 22:55
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,q[N*N][2],ans;
char ch[N][N];
bool b[N][N]; 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void bfs(int x,int y)
{
	int head=0,tail=1;
	q[tail][0]=x,q[tail][1]=y;
	b[x][y]=true;	
	while(head<tail)
	{
		for(int i=0;i<=3;i++)
		{
			int px=x+dx[i],py=y+dy[i];
			if(px>=1&&px<=n&&py>=1&&py<=m&&!b[px][py])
			{
				tail++;
				q[tail][0]=px,q[tail][1]=py;
				b[px][py]=true;
			}
		}
	}
}
bool pd(int x,int y)
{
	int cnt=0;
	if(ch[x][y]=='#') cnt++;
	if(ch[x+1][y]=='#') cnt++;
	if(ch[x][y+1]=='#') cnt++;
	if(ch[x+1][y+1]=='#') cnt++;
	if(cnt==3) return true;
	return false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>ch[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(pd(i,j))
			{
				cout<<"Bad placement.\n";
				return 0;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(ch[i][j]=='#'&&!b[i][j])
			{
				bfs(i,j);
				ans++;
			}
		}
	printf("There are %d ships.",ans);
	return 0;
}
2024/12/5 22:55
加载中...