codeforces #375 D. Lakes in Berland (dfs)

Posted by 111qqz on Monday, October 3, 2016

TOC

题目链接

题意: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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付