首页 > 代码库 > Codeforces 723d [暴力dfs]

Codeforces 723d [暴力dfs]

/*不要低头,不要放弃,不要气馁,不要慌张。题意:给n,m和k,n和m为所给矩阵的高和宽。k是要求最多剩下的湖的数量。在所给的矩阵中,*代表陆地,.代表水。湖的定义是一片连续的水(上下左右四个方向),并且水不含边界。水含边界的情况被成为海。问最少填多少湖的面积,使得湖的数量减少到k...思路:水dfs,记录有多少湖,并且记录每个湖的面积,然后排下序贪心就好。坑:做题一定别急一定别急一定别急一定知道自己写的是什么!!!!*/#include<bits/stdc++.h>using namespace std;int n,m,ans,gg;int zhx[]={-1,0,1,0};int zhy[]={0,1,0,-1};char pho[55][55];bool vis[55][55];int jilu[55][55];struct st{    st(){}    st(int a,int b){        id=a;num=b;    }    int id;    int num;};vector<st>mv;bool inmap(int x,int y){    if(x<1||x>n||y<1||y>m)return 0;    return pho[x][y]==.;}bool dfs(int x,int y){    vis[x][y]=1;    jilu[x][y]=gg;    ans++;    bool ok=1;    for(int i=0;i<4;i++){        int xx=x+zhx[i];        int yy=y+zhy[i];        if(inmap(xx,yy)&&!vis[xx][yy]){            ok&=dfs(xx,yy);        }    }    if(x==1||x==n||y==1||y==m)return 0;    return ok;}bool cmp(st a,st b){    return a.num<b.num;}int main(){    gg=1;    int k;    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++)scanf("%s",pho[i]+1);    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            if(vis[i][j]==0&&pho[i][j]==.){                ans=0;                gg++;                if(dfs(i,j))mv.push_back(st(gg,ans));            }        }    }    if(mv.size())sort(mv.begin(),mv.end(),cmp);    int zong=0;    for(int i=0;i<mv.size()-k;i++){        for(int j=1;j<=n;j++){            for(int w=1;w<=m;w++){                if(jilu[j][w]==mv[i].id)pho[j][w]=*;            }        }        zong+=mv[i].num;    }    printf("%d\n",zong);    for(int i=1;i<=n;i++){        puts(pho[i]+1);    }}

 

Codeforces 723d [暴力dfs]