开O2M,关O2T #6#8。求原因
  • 板块P1331 海战
  • 楼主UKE_Piu
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/15 13:36
  • 上次更新2024/7/15 14:39:08
查看原帖
开O2M,关O2T #6#8。求原因
787031
UKE_Piu楼主2024/7/15 13:36
#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int n,m;
int ans;
const int N=1e3+3;
int a[N][N];
bool F=true,vis[N][N];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool Break(int x,int y){
	return vis[x][y] || (a[x][y]==0) || (x<1||y<1||x>n||y>m);
}
struct node {
	int x,y;
};

void bfs(int i,int j){
	queue<node> q;
	node tmp;
	tmp.x=i; tmp.y=j;
	q.push(tmp);
	vis[i][j]=true;
	while(!q.empty()){
	//	cout<<"Begin to BFS\n";
		tmp=q.front(); q.pop();
		int ux=tmp.x,uy=tmp.y;
		vis[ux][uy]=true;
		for(int k=0;k<4;k++){
	//		cout<<"Expanding Outward\n";
			int vx=ux+dx[k];
			int vy=uy+dy[k];
			if(!Break(vx,vy)){
	//			cout<<"Push ( node { "<<vx<<" , "<<vy<<" } )\n";
				q.push(node{vx,vy});
			}
		}
	}
	ans++;
}

void check(){
	for(int i=1;i<=n;i++){
	  for(int j=1;j<=m;j++){
	  	int sum=0;
		for(int k=0;k<2;k++){
	      for(int p=0;p<2;p++){
	      	sum+=a[i+k][j+p];
		  }
		}
		if(sum==3) F=false;
      }
	}
}

void print(){
	cout<<"--------"<<ans<<"-----------\n";
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++){
			cout<< ( vis[i][j] ? 1:0 ) <<' ';
		}
		cout<<endl;
	}
	cout<<"\n\n\n";
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	char c; cin>>c;
	  	if(c=='#') a[i][j]=1;
	  	else a[i][j]=0;
	  }
	check();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++){
	  	if(!vis[i][j]&&a[i][j]){
//	  		cout<<i<<' '<<j<<'\n';
	  		bfs(i,j);
//	  		print();
		  }
	  }
//	cout<<"\n\n\n";
	if(F) cout<<"There are "<<ans<<" ships.";
	else cout<<"Bad placement.";
	return 0;
}
2024/7/15 13:36
加载中...