#6MLE求条
  • 板块P1331 海战
  • 楼主volatile
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/4/25 21:20
  • 上次更新2025/6/17 12:58:38
查看原帖
#6MLE求条
772464
volatile楼主2025/4/25 21:20
#include<iostream>
#include<queue>
using namespace std;
struct ship{
    int x,y;
};
int sea[1145][1145],r,c;
int f[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
queue<ship>q,re;
int fun(int i,int j)
{
    int t=0;
    if(sea[i][j]) t++;
    if(sea[i+1][j]) t++;
    if(sea[i][j+1]) t++;
    if(sea[i+1][j+1]) t++;
    if(t==3) return 1;
    return 0;
}
void bfs()
{
    while(!q.empty()){
        sea[q.front().x][q.front().y]=0;
        for(int i=0;i<=3;i++){
            ship now;
            now.x=q.front().x+f[i][0];
            now.y=q.front().y+f[i][1];
            if(sea[now.x][now.y]) q.push(now);
        }
        q.pop();
    }
    q=re;
}
int main()
{
    int sum=0;
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            char ch;
            cin>>ch;
            if(ch=='#') sea[i][j]=1;
        }
    }
    for(int i=1;i<r;i++){
        for(int j=1;j<c;j++){
            if(fun(i,j)){
                cout<<"Bad placement.";
                return 0;
            }
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(sea[i][j]){
                sum++;
                ship t;
                t.x=i;
                t.y=j;
                q.push(t);
                bfs();
            }
        }
    }
    cout<<"There are "<<sum<<" ships.";
    return 0;
}

thx

2025/4/25 21:20
加载中...