首页 > 代码库 > 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]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。