55求助
  • 板块P1331 海战
  • 楼主wyzths
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/6 11:27
  • 上次更新2024/8/6 12:40:30
查看原帖
55求助
1382435
wyzths楼主2024/8/6 11:27
#include <iostream>
#include <queue>
using namespace std;
int n,m,ans;
int a[1010][1010];
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
struct node{
	int x,y;
};
void bfs(int x,int y){
	queue<node> q;
	node tmp = {x,y};
	q.push(tmp);
	while(q.size()){
		tmp = q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int nx = tmp.x+dir[i][0];
			int ny = tmp.y+dir[i][1];
			if(nx<1||ny<1||nx>n||ny>m) continue;
			if(a[nx][ny]){
				a[nx][ny] = false;
				q.push({nx,ny});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	char c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			a[i][j] = (c=='#');
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
			if(a[i][j]==false){
				continue;
			}
			int num=0;
			for(int k=0;k<=3;k++){
				int nx = i+dir[k][0];
				int ny = j+dir[k][1];
				if(a[nx][ny]){
					num++;
				}
			}
			if(num==3){
				printf("Bad placement.");
				return 0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]!=0){
				bfs(i,j);
				ans++;
			}
		}
	}
	printf("There are %d ships.",ans);
	return 0;
}
2024/8/6 11:27
加载中...