81分
  • 板块P1331 海战
  • 楼主Tsuki091117
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/12 19:18
  • 上次更新2024/1/12 19:20:08
查看原帖
81分
1069816
Tsuki091117楼主2024/1/12 19:18
#include<bits/stdc++.h>
#define int long long
using namespace std;
int r,c,h=1,t,ans;
int b[10000100][5];
bool f[1010][1010];
int fx[5]={0,0,1,0,-1};
int fy[5]={0,1,0,-1,0};
char a[1010][1010];
bool pd(int x,int y){
	int cnt=0;
	if(a[x][y]=='#'){
		cnt++;
	}
	if(a[x+1][y]=='#'){
		cnt++;
	}
	if(a[x][y+1]=='#'){
		cnt++;
	}
	if(a[x+1][y+1]=='#'){
		cnt++;
	}
	if(c==3){
		return 0;
	}
	return 1;
}
void bfs(int x,int y){
	if(f[x][y]){
		return;
	}
	b[++t][1]=x;
	b[t][2]=y;
	ans++;
	while(h<=t){
		for(int i=1;i<=4;i++){
			int tx=b[h][1]+fx[i];
			int ty=b[h][2]+fy[i];
			if(tx>=1&&ty<=c&&ty>=1&&tx<=r&&!f[tx][ty]&&a[tx][ty]=='#'){
				f[tx][ty]=1;
				t++;
				b[t][1]=tx;
				b[t][2]=ty;
			}
		}
		h++;
	}
	f[x][y]=1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<r;i++){
		for(int j=1;j<c;j++){
			if(!pd(i,j)){
				cout<<"Bad placement.";
				return 0;
			}
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(a[i][j]=='#'){
				bfs(i,j);
			}
		}
	}
	cout<<"There are "<<ans<<" ships.";
	return 0;
}
2024/1/12 19:18
加载中...