codeforces #375 D. Lakes in Berland (dfs)
题意：nm个格子，有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个nm的图保证至少有k个湖。问填多少个.成，才能使得恰好有k个湖。
思路：贪心，先处理出所有的湖的大小，然后从小往大填。
注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。
/* ***********************************************
Author :111qqz
Created Time :2016年10月03日 星期一 21时18分03秒
File Name :code/cf/#375/D.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <bitset>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};tanxin
const int inf = 0x3f3f3f3f;
const int N=55;
char maze[N][N];
int n,m,k;
int vis[N][N];
int lake_cnt=0;
int siz;
struct node
{
int id;
int val;
bool operator < (node b)const
{
return val<b.val;
}
}lake[N*N];
bool die ;
set< pi >se;
void dfs( int x,int y)
{
if (die) return;
siz++;
// cout<<"x:"<<x<<" y: "<<y<<endl;
for ( int i = 0 ; i < 4 ; i++)
{
int nx = x + dx4[i];
int ny = y + dy4[i];
if (maze[nx][ny]=='*') continue;
if (nx==0||nx==n-1||ny==0||ny==m-1)
{
die = true;
return;
}
if (vis[nx][ny]!=0) continue;
vis[nx][ny] = lake_cnt;
se.insert(make_pair(nx,ny));
dfs(nx,ny);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
cin>>n>>m>>k;
for ( int i = 0 ; i < n ; i++) scanf("%s",maze[i]);
ms(vis,0);
for ( int i = 1 ; i < n-1 ; i++)
{
for ( int j = 1 ; j < m-1 ; j++)
{
if (maze[i][j]=='.'&&!vis[i][j])
{
se.clear();
siz = 0 ;
vis[i][j] = ++lake_cnt;
se.insert(make_pair(i,j));
die = false;
dfs(i,j);
if (die)
{
for ( auto it = se.begin () ; it!=se.end() ;it++)
{
pi tmp = *it;
vis[tmp.fst][tmp.sec] = 0 ;
}
lake_cnt--;
}
else
{
lake[lake_cnt].val=siz;
lake[lake_cnt].id = lake_cnt;
}
}
}
}
sort(lake+1,lake+lake_cnt+1);
map<int,int>mp;
for ( int i = 1 ; i <= lake_cnt ; i++) mp[lake[i].id] = i;
// for ( int i = 0 ; i < n ; i++)
// {
// for ( int j = 0 ; j < m ; j++)
// {
// printf("%d ",vis[i][j]);
// }
// printf("\n");
// }
for ( int i = 1 ; i < n-1 ; i++)
{
for ( int j = 1 ; j < m-1; j++)
{
if (maze[i][j]=='*') continue;
int v = vis[i][j];
if (v==0) continue;
if (mp[v]<=lake_cnt-k) maze[i][j]='*';
}
}
int ans = 0 ;
for ( int i = 1 ; i <= lake_cnt-k ; i++) ans = ans + lake[i].val;
printf("%d\n",ans);
for ( int i = 0 ; i < n ; i++) printf("%s\n",maze[i]);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}