【Codeforces 723D】Lakes in Berland （dfs）

海洋包围的小岛，岛内的有湖，'.'代表水，'*'代表陆地，给出的n*m的地图里至少有k个湖，求填掉面积尽量少的水，使得湖的数量正好为k。

dfs找出所有水联通块，判断一下是否是湖（海水区非湖）。将湖按面积排序，若湖的数量为cnt，填掉前cnt-k个湖。

http://codeforces.com/problemset/problem/723/D

Examples

input

代码语言：javascript复制

5 4 1
****
*..*
****
**.*
..**

output

代码语言：javascript复制

1
****
*..*
****
****
..**

input

代码语言：javascript复制

3 3 0
***
*.*
***

output

代码语言：javascript复制

1
***
***
***

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
int n,m,k;
char a[55][55];
bool vis[55][55];
int dx[6]={0,0,1,-1};
int dy[6]={1,-1,0,0};

int num,cnt,islake;
int ans;
struct lake{
    int x,y;
    int num;
    int id;
}lk[3600];
bool cmp(lake a,lake b){
    return a.num<b.num;
}
void dfs(int x,int y){
    vis[x][y]=1;
    num  ;
    if(x==0||x==n-1||y==0||y==m-1)islake=0;
    for(int i=0;i<4;i  ){
        int nx=x dx[i],ny=y dy[i];
        if(nx>=0&&nx<n&&ny<m&&ny>=0&&a[nx][ny]=='.'&&!vis[nx][ny])
            dfs(nx,ny);
    }
}
void fil(int x,int y,int id){
    vis[x][y]=1;
    ans  ;
    a[x][y]='*';
    for(int i=0;i<4;i  ){
        int nx=x dx[i],ny=y dy[i];
        if(nx>=0&&nx<n&&ny<m&&ny>=0&&a[nx][ny]=='.'&&!vis[nx][ny])
            fil(nx,ny,id);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i  )
            scanf(" %s",a[i]);
    for(int i=0;i<n;i  )
        for(int j=0;j<m;j  )
            if(!vis[i][j]&&a[i][j]=='.'){
                num=0;
                islake=1;
                dfs(i,j);
                if(islake)lk[cnt  ]=(lake){i,j,num,cnt};
            }
    memset(vis,0,sizeof vis);
    sort(lk,lk cnt,cmp);
    for(int l=0;l<cnt-k;l  )
        for(int i=0;i<n;i  )
            for(int j=0;j<m;j  )
                if(i==lk[l].x&&j==lk[l].y)
                    fil(i,j,lk[l].id);
    printf("%dn",ans);
    for(int i=0;i<n;i  )
        printf("%sn",a[i]);
}

dfs input output 排序

0 人点赞