help 广搜73分
查看原帖
help 广搜73分
990278
NEGATUIVE_SEVEN_DL楼主2023/8/18 12:11
using namespace std;
struct pos
{
	int x,y;
};
int book[1250][1250],n,m,cnt=0,ans=0;
int posx[4]={-1,0,1,0};
int posy[4]={0,0,1,-1};
char mapn[1250][1250];
queue <pos> q;
void bfs(int x,int y)
{
	book[x][y]=1;
	pos u;
	u.x=x;
	u.y=y;
	q.push(u);
	while(q.empty()==0)
	{
		pos v=q.front();
		for(int i=0;i<4;i++)
		{
			int a=v.x+posx[i];
			int b=v.y+posy[i];
			if(a>=1&&a<=n&&b>=1&&b<=m)
			{
				if(book[a][b]==0&&mapn[a][b]=='#')
				{
					book[a][b]=1;
					pos t;
					t.x=a;
					t.y=b;
					q.push(t);
				}
			}
		}
		q.pop();
	}
}
bool zc(int x,int y)
{
	ans=0;
	if(mapn[x][y]=='#') ans++;
	if(mapn[x][y+1]=='#') ans++;
	if(mapn[x+1][y]=='#') ans++;
	if(mapn[x+1][y+1]=='#') ans++;
	if(ans==3)
	{
		return 0;
	}
	return 1;
}
int main()
{
	cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		cin>>mapn[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
	    	if(zc(i,j)==0)
	    	{
	    		cout<<"Bad placement.";
	    		return 0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=m;j++)
	    {
		    if(mapn[i][j]=='#'&&book[i][j]==0)
		    {
		        bfs(i,j);
				cnt++;
		    }
	    }
	}
	cout<<"There are "<<cnt<<" ships.";
    return 0;
}
2023/8/18 12:11
加载中...