BFS 82求调
查看原帖
BFS 82求调
1057966
youlunkubiaoke楼主2024/8/2 21:46

#6MLE,#11WA,求调

#pragma GCC optimize(3)
#include<iostream>
#include<queue>
using namespace std;
typedef unsigned long long int UL;
typedef long long int LL;
typedef unsigned short US;
typedef double DB;
struct Node
{
    LL x;
    LL y;
};
char sea[1002][1002]={0};
bool visited[1002][1002]={false};
LL BFS(LL y,LL x)
{
    queue<Node> q;
    LL minx=999999999,maxx=0,miny=999999999,maxy=0;
    Node node;
    node.x=x;
    node.y=y;
    q.push(node);
    while (q.empty()!=true)
    {
        node=q.front();
        q.pop();
        visited[node.y][node.x]=true;
        if (sea[node.y-1][node.x]=='#'&&visited[node.y-1][node.x]!=true)
        {
            node.y=node.y-1;
            node.x=node.x;
            if (node.x<minx)
              minx=node.x;
            if (node.y>maxy)
              maxy=node.y;
            if (node.x>maxx)
              maxx=node.x;
            if (node.y<miny)
              miny=node.y;
            q.push(node);
        }
        if (sea[node.y+1][node.x]=='#'&&visited[node.y+1][node.x]!=true)
        {
            node.y=node.y+1;
            node.x=node.x;
            if (node.x<minx)
              minx=node.x;
            if (node.y>maxy)
              maxy=node.y;
            if (node.x>maxx)
              maxx=node.x;
            if (node.y<miny)
              miny=node.y;
            q.push(node);
        }
        if (sea[node.y][node.x-1]=='#'&&visited[node.y][node.x-1]!=true)
        {
            node.y=node.y;
            node.x=node.x-1;
            if (node.x<minx)
              minx=node.x;
            if (node.y>maxy)
              maxy=node.y;
            if (node.x>maxx)
              maxx=node.x;
            if (node.y<miny)
              miny=node.y;
            q.push(node);
        }
        if (sea[node.y][node.x+1]=='#'&&visited[node.y][node.x+1]!=true)
        {
            node.y=node.y;
            node.x=node.x+1;
            if (node.x<minx)
              minx=node.x;
            if (node.y>maxy)
              maxy=node.y;
            if (node.x>maxx)
              maxx=node.x;
            if (node.y<miny)
              miny=node.y;
            q.push(node);
        }
    }
    for (LL x1=minx;x1<=maxx;x1++)
    {
        for (LL y1=miny;y1<=maxy;y1++)
        {
            if (sea[y1][x1]!='#')
              return -1;
        }
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(false);
    LL n,m,flag,sum=0;
    cin>>n>>m;
    for (LL n1=1;n1<=n;n1++)
    {
        for (LL m1=1;m1<=m;m1++)
        {
            cin>>sea[n1][m1];
        }
    }
    for (LL n1=1;n1<=n;n1++)
    {
        for (LL m1=1;m1<=m;m1++)
        {
            if (sea[n1][m1]=='#'&&visited[n1][m1]==false)
            {
                flag=BFS(n1,m1);
                if (flag==-1)
                {
                    cout<<"Bad placement."<<endl;
                    return 0;
                }
                else
                  sum++;
            }
        }
    }
    cout<<"There are "<<sum<<" ships."<<endl;
    return 0;
}
2024/8/2 21:46
加载中...