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