bfs12分求助

P8662 [蓝桥杯 2018 省 AB] 全球变暖

cyz_czy @ 2023-05-21 12:24:23


#include <iostream>
#include <queue>

const int N=1e3+1e1;

bool l[N][N];
bool p[N][N];

int m;
int c;

void input(){
    scanf("%d",&m);

    char a;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++){

            std::cin>>a;
            if(a=='#')
                l[i][j]=true;
        }

    return ;
}

struct st{
    int x,y;
};

std::queue<st> q;

const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};

void bfs(){
    while(!q.empty()){
        int tx=q.front().x;
        int ty=q.front().y;

        p[tx][ty]=true;

        q.pop();

        bool a=false;

        for(int i=0;i<4;i++){

            int tempx=tx+dx[i];
            int tempy=ty+dy[i];

            if(tempx<1||tempx>m||tempy<1||tempy>m)
                continue;

            if(!l[tempx][tempy])
                a=true;
        }

        if(!a)
            c++;

        for(int i=0;i<4;i++){

            int tempx=tx+dx[i];
            int tempy=ty+dy[i];

            if(tempx<1||tempx>m||tempy<1||tempy>m||!l[tempx][tempy]||p[tempx][tempy])
                continue;

            q.push(st{tempx,tempy});

            p[tempx][tempy]=true;
        }
    }

    while(!q.empty())
        q.pop();

    return ;
}

int main(){
    input();

    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            if(l[i][j]&&!p[i][j])
                q.push(st{i,j}),bfs();

    printf("%d",c);

    return 0;
}

by Cubic @ 2023-05-21 12:30:24

我靠你码风变屌了啊。


by cyz_czy @ 2023-05-21 17:30:52

@Cubic 什么玩意?


|