CF723D 【Lakes in Berland】

时间：2023-03-09 17:49:57
CF723D 【Lakes in Berland】

题目链接

题解 CF723D 【Lakes in Berland】

首先将边界的水用bfs处理掉

再将中间的每一个湖泊处理出来，存入一个结构体内，结构体里记录湖泊大小和开始点

将湖泊排序从小往大填满，并利用开始点进行bfs改变地图

细节见代码：

#include<bits/stdc++.h>

using namespace std;

int n,m,k;

int vis[][],mapp[][];

int dx[]={,-,,,};

int dy[]={,,,,-},cnt;

struct SYM{

    int cc,sx,sy;

}lake[];

void bfs(int x,int y,int opt){

     queue<int> qx,qy;int siz=;

     if(opt==){                      //处理边界

        vis[x][y]=;qx.push(x);qy.push(y);

        while(!qx.empty()){

              int xx=qx.front(),yy=qy.front();qx.pop();qy.pop();

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

                  int nx=xx+dx[i],ny=yy+dy[i];

                  if(nx==||ny==||nx==n+||ny==m+) continue;

                  if(vis[nx][ny]) continue;

                  vis[nx][ny]=;

                  qx.push(nx);qy.push(ny);

              }

        }

     }

     if(opt==){                     //处理湖泊

        vis[x][y]=;qx.push(x);qy.push(y);

        while(!qx.empty()){

              int xx=qx.front(),yy=qy.front();qx.pop();qy.pop();

              siz++;

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

                  int nx=xx+dx[i],ny=yy+dy[i];

                  if(nx==||ny==||nx==n+||ny==m+) continue;

                  if(vis[nx][ny]) continue;

                  vis[nx][ny]=;

                  qx.push(nx);qy.push(ny);

              }

        }

        lake[++cnt].cc=siz;lake[cnt].sx=x;lake[cnt].sy=y; //存入湖泊大小和开始点

     }

     if(opt==){                //改变地图

        mapp[x][y]=;qx.push(x);qy.push(y);

        while(!qx.empty()){

              int xx=qx.front(),yy=qy.front();qx.pop();qy.pop();

              siz++;

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

                  int nx=xx+dx[i],ny=yy+dy[i];

                  if(nx==||ny==||nx==n+||ny==m+) continue;

                  if(mapp[nx][ny]) continue;

                  mapp[nx][ny]=;

                  qx.push(nx);qy.push(ny);

              }

        }

     }

}

bool cmp(const SYM &a,const SYM &b){

     return a.cc>b.cc;

}

int main(){

    char c[];

    scanf("%d%d%d",&n,&m,&k);

    for(int i=;i<=n;i++){

        scanf("%s",c);

        for(int j=;j<m;j++)

            mapp[i][j+]=vis[i][j+]=(c[j]=='*');

    }

    for(int i=;i<=n;i++){                       //处理边界水

        if(mapp[i][]==&&vis[i][]==) bfs(i,,);

        if(mapp[i][m]==&&vis[i][m]==) bfs(i,m,);

    }

    for(int i=;i<=m;i++){

        if(mapp[][i]==&&vis[][i]==) bfs(,i,);

        if(mapp[n][i]==&&vis[n][i]==) bfs(n,i,);

    }

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            if(!vis[i][j]) bfs(i,j,);

    sort(lake+,lake+cnt+,cmp);                  //湖泊按大小排序

    int ans=;

    while(cnt>k){                           //填湖泊

          ans+=lake[cnt].cc;

          bfs(lake[cnt].sx,lake[cnt].sy,);       //改地图

          cnt--;

    }

    printf("%d\n",ans);

    for(int i=;i<=n;i++){

        for(int j=;j<=m;j++){

            if(mapp[i][j]==) printf("*");

            else printf(".");

        }

        printf("\n");

    }

    return ;

}

相关文章