codeforces #375 D. Lakes in Berland (dfs)
题意：nm个格子，有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个nm的图保证至少有k个湖。问填多少个.成，才能使得恰好有k个湖。
思路：贪心，先处理出所有的湖的大小，然后从小往大填。
注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年10月03日 星期一 21时18分03秒
4File Name :code/cf/#375/D.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <deque>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <bitset>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27using namespace std;
28const double eps = 1E-8;
29const int dx4[4]={1,0,0,-1};
30const int dy4[4]={0,-1,1,0};tanxin
31const int inf = 0x3f3f3f3f;
32const int N=55;
33char maze[N][N];
34int n,m,k;
35int vis[N][N];
36int lake_cnt=0;
37int siz;
38struct node
39{
40 int id;
41 int val;
42 bool operator < (node b)const
43 {
44 return val<b.val;
45 }
46}lake[N*N];
47bool die ;
48set< pi >se;
49void dfs( int x,int y)
50{
51 if (die) return;
52 siz++;
53// cout<<"x:"<<x<<" y: "<<y<<endl;
54 for ( int i = 0 ; i < 4 ; i++)
55 {
56 int nx = x + dx4[i];
57 int ny = y + dy4[i];
58 if (maze[nx][ny]=='*') continue;
59 if (nx==0||nx==n-1||ny==0||ny==m-1)
60 {
61 die = true;
62 return;
63 }
64 if (vis[nx][ny]!=0) continue;
65 vis[nx][ny] = lake_cnt;
66 se.insert(make_pair(nx,ny));
67 dfs(nx,ny);
68 }
69}
70int main()
71{
72 #ifndef ONLINE_JUDGE
73 freopen("code/in.txt","r",stdin);
74 #endif
75 cin>>n>>m>>k;
76 for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
77 ms(vis,0);
78 for ( int i = 1 ; i < n-1 ; i++)
79 {
80 for ( int j = 1 ; j < m-1 ; j++)
81 {
82 if (maze[i][j]=='.'&&!vis[i][j])
83 {
84 se.clear();
85 siz = 0 ;
86 vis[i][j] = ++lake_cnt;
87 se.insert(make_pair(i,j));
88 die = false;
89 dfs(i,j);
90 if (die)
91 {
92 for ( auto it = se.begin () ; it!=se.end() ;it++)
93 {
94 pi tmp = *it;
95 vis[tmp.fst][tmp.sec] = 0 ;
96 }
97 lake_cnt--;
98 }
99 else
100 {
101 lake[lake_cnt].val=siz;
102 lake[lake_cnt].id = lake_cnt;
103 }
104 }
105 }
106 }
107 sort(lake+1,lake+lake_cnt+1);
108 map<int,int>mp;
109 for ( int i = 1 ; i <= lake_cnt ; i++) mp[lake[i].id] = i;
110// for ( int i = 0 ; i < n ; i++)
111// {
112// for ( int j = 0 ; j < m ; j++)
113// {
114// printf("%d ",vis[i][j]);
115// }
116// printf("\n");
117// }
118 for ( int i = 1 ; i < n-1 ; i++)
119 {
120 for ( int j = 1 ; j < m-1; j++)
121 {
122 if (maze[i][j]=='*') continue;
123 int v = vis[i][j];
124 if (v==0) continue;
125 if (mp[v]<=lake_cnt-k) maze[i][j]='*';
126 }
127 }
128 int ans = 0 ;
129 for ( int i = 1 ; i <= lake_cnt-k ; i++) ans = ans + lake[i].val;
130 printf("%d\n",ans);
131 for ( int i = 0 ; i < n ; i++) printf("%s\n",maze[i]);
132 #ifndef ONLINE_JUDGE
133 fclose(stdin);
134 #endif
135 return 0;
136}