codeforces #375 D. Lakes in Berland (dfs)

题目链接

题意：n*m个格子，有*和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个n*m的图保证至少有k个湖。问填多少个.成*，才能使得恰好有k个湖。

思路：贪心，先处理出所有的湖的大小，然后从小往大填。

注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。

 

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
 
 
 
/* ***********************************************
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;
}
 
 
 
 

 

作者： CrazyKK

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz