46分bfs
  • 板块P1331 海战
  • 楼主yyc1231
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/28 11:43
  • 上次更新2024/7/28 13:50:30
查看原帖
46分bfs
1091120
yyc1231楼主2024/7/28 11:43
#include<bits/stdc++.h>
using namespace std;
#define ll long long

struct sNode{
	int row;
	int col;
};

int r,c,vis[40][40],board[40][40],bias_x[4]={-1,1,0,0},bias_y[4]={0,0,-1,1},color;
queue <sNode>qu;
char t;
void bfs(int x,int y){
	sNode sn={};
	sn.row=x;
	sn.col=y;
	qu.push(sn);
	board[x][y]=color;
	while(qu.size()){
		sNode sn_t=qu.front();
		qu.pop();
		for(int i=0;i<4;i++){
			int row=sn_t.row;
			int col=sn_t.col;
			row+=bias_x[i];
			col+=bias_y[i];
			if(board[row][col]==-1){
				board[row][col]=color;
				sNode sn_new={};
				sn_new.row=row;
				sn_new.col=col;
				qu.push(sn_new);
			}
		}
	}		
}

int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>t;
			if(t=='#')board[i][j]=-1;
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(board[i][j]==-1)color++,bfs(i,j);
		}
	}
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			if(board[i][j]>0&&board[i][j+1]==0&&board[i+1][j+1]>0&&board[i+1][j]>0){
				cout<<"Bad placement.";
				return 0;
			}
			if(board[i][j]>0&&board[i][j+1]>0&&board[i+1][j+1]>0&&board[i+1][j]>0){
				cout<<"Bad placement.";
				return 0;
			}
			if(board[i][j]>0&&board[i][j+1]>0&&board[i+1][j+1]==0&&board[i+1][j]==0){
				cout<<"Bad placement.";
				return 0;
			}
			if(board[i][j]==0&&board[i][j+1]>0&&board[i+1][j+1]>0&&board[i+1][j]>0){
				cout<<"Bad placement.";
				return 0;
			}
		}
	}
	printf("There are %d ships.",color);
	return 0;
} 
2024/7/28 11:43
加载中...