首页 > 代码库 > 【Codeforces 723D】Lakes in Berland （dfs）
【Codeforces 723D】Lakes in Berland （dfs）
海洋包围的小岛，岛内的有湖，‘.‘代表水，‘*‘代表陆地，给出的n*m的地图里至少有k个湖，求填掉面积尽量少的水，使得湖的数量正好为k。
dfs找出所有水联通块，判断一下是否是湖（海水区非湖）。将湖按面积排序，若湖的数量为cnt，填掉前cnt-k个湖。
http://codeforces.com/problemset/problem/723/D
Examples
input
5 4 1
****
*..*
****
**.*
..**
output
1
****
*..*
****
****
..**
input
3 3 0
***
*.*
***
output
1
***
***
***
#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("%d\n",ans); for(int i=0;i<n;i++) printf("%s\n",a[i]);}
【Codeforces 723D】Lakes in Berland （dfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。