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 long using 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; }
