bfs46求调
查看原帖
bfs46求调
1054021
114_Hzh_AK_NOIP_514楼主2024/6/28 21:09
#include<bits/stdc++.h>
using namespace std;
int r,c;
char mapp[1010][1010];
int d[4][2]={0,-1,1,0,-1,0,0,1};
int dfs(int x,int y)
{
	mapp[x][y]='*';
	for(int i=0;i<4;i++)
	{
		int nx=x+d[i][0];
		int ny=y+d[i][1];
		if(nx<1 || ny<1 || nx>r || ny>c) continue;
		if(mapp[nx][ny]=='#') dfs(nx,ny);
	}
}
bool d(int i,int j)
{
	int c=0;
	if(mapp[i][j]=='#')c++;
	if(mapp[i+1][j]=='#')c++;
	if(mapp[i][j+1]=='#')c++;
	if(mapp[i+1][j+1]=='#')c++;
	if(c==3) return 0;
	return 1;
}
int main()
{
	scanf("%d%d",&r,&c);
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>mapp[i][j];
		}
	}
	int s=0;
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			if(i<r&&j<c&&d(i,j)==0)
			{
				printf("Bad placement.");
				return 0;
			}
		}
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
			if(mapp[i][j]=='#')
			{
				s++;
				dfs(i,j);	
			}
		}
	}
	printf("There are %d ships.",s);
	return 0;
}
2024/6/28 21:09
加载中...