首页 > 代码库 > CF #375 (Div. 2) D. bfs
CF #375 (Div. 2) D. bfs
1、CF #375 (Div. 2) D. Lakes in Berland
2、总结:麻烦的bfs,但其实很水。。
3、题意:n*m的陆地与水泽,水泽在边界表示连通海洋。最后要剩k个湖,总要填掉多少个湖,然后输出。
#include<bits/stdc++.h>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=2100,MAX=1000100;struct Node{ int i,j,num; bool operator < (const Node &a)const{ return num>a.num; }};int n,m,k,num,flag;int diri[4]={0,0,1,-1};int dirj[4]={1,-1,0,0};int vis[80][80];char mapn[80][80];bool charge(Node e){ if(mapn[e.i][e.j]==‘.‘&&e.i>=0&&e.i<n&&e.j>=0&&e.j<m&&!vis[e.i][e.j]) return true; return false;}bool charge2(Node e){ if(e.i==0||e.i==n-1||e.j==0||e.j==m-1) return true; return false;}void bfs(int i,int j){ queue<Node>Q; Node st,en; st.i=i,st.j=j; vis[i][j]=1; Q.push(st); if(charge2(st)){flag=0;} while(!Q.empty()) { st=Q.front();Q.pop(); F(l,0,4){ en.i=st.i+diri[l]; en.j=st.j+dirj[l]; if(charge(en)){ if(charge2(en))flag=0; vis[en.i][en.j]=1; Q.push(en); num++; } } }}void bfs2(int i,int j){ queue<Node>Q; Node st,en; st.i=i,st.j=j; vis[i][j]=1; Q.push(st); while(!Q.empty()) { st=Q.front();Q.pop(); F(l,0,4){ en.i=st.i+diri[l]; en.j=st.j+dirj[l]; if(mapn[en.i][en.j]==‘.‘){ mapn[en.i][en.j]=‘*‘; Q.push(en); } } }}int main(){ while(~scanf("%d%d%d",&n,&m,&k)) { int num1=0; priority_queue<Node>Q; mes(vis,0); F(i,0,n)scanf("%s",mapn[i]); F(i,0,n) F(j,0,m){ if(mapn[i][j]==‘.‘&&i>=0&&i<n&&j>=0&&j<m&&!vis[i][j]){ num=1,flag=1; bfs(i,j); if(flag){ num1++; Node ans;ans.i=i,ans.j=j,ans.num=num; Q.push(ans); } } } mes(vis,0); int sum=0; num1-=k; while(num1--){ Node ans=Q.top();Q.pop(); sum+=ans.num; mapn[ans.i][ans.j]=‘*‘; bfs2(ans.i,ans.j); } cout<<sum<<endl; F(i,0,n)printf("%s\n",mapn[i]); } return 0;}
CF #375 (Div. 2) D. bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。