Codeforces Round #375 (Div. 2) D. Lakes in Berland DFS

D. Lakes in Berland

链接：

http://codeforces.com/problemset/problem/723/D

题意

给你一个n/*m的矩阵，然后你们有不少于k条湖泊，然后你需要使得一些湖泊变成陆地，使得湖泊的数量恰好等于k，问你至少填多少个水。

湖泊不与外界相邻。

题解：

直接dfs搜出每一条湖泊，然后放在优先队列里，从小到大去填满就好了。

代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<vector>
 4 #include<functional>
 5 using namespace std;
 6 
 7 typedef pair<int, int> P;
 8 typedef pair<int, P> PP;
 9 const int maxn = 55;
10 char map[maxn][maxn];
11 int vis[maxn][maxn];
12 int dx[4] = { 1,0,-1,0 };
13 int dy[4] = { 0,1,0,-1 };
14 int n, m, sum, fg;
15 priority_queue<PP, vector<PP>, greater<PP> > lake;
16 
17 void dfs(P s)
18 {
19     int x = s.first, y = s.second;
20     sum++;
21     vis[x][y] = 1;
22     if (x == 1 || x == n || y == 1 || y == m) fg = 0;
23     for (int i = 0; i < 4; i++)
24     {
25         int nx = x + dx[i];
26         int ny = y + dy[i];
27         if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
28             map[nx][ny] == '.' && !vis[nx][ny]) 
29         dfs(P(nx, ny));
30     }
31 }
32 
33 void dfs2(P s)
34 {
35     int x = s.first, y = s.second;
36     map[x][y] = '*';
37     for (int i = 0; i < 4; i++)
38     {
39         int nx = x + dx[i];
40         int ny = y + dy[i];
41         if (nx >= 1 && nx <= n && ny >= 1 && ny <= m &&
42             map[nx][ny] == '.')
43             dfs2(P(nx, ny));
44     }
45 }
46 
47 int main()
48 {
49     int k;
50     cin >> n >> m >> k;
51     for (int i = 1; i <= n; i++)
52         for (int j = 1; j <= m; j++)
53             cin >> map[i][j];
54     for (int i = 1; i <= n; i++)
55         for (int j = 1; j <= m; j++)
56             if (map[i][j] == '.' && vis[i][j] == 0) {
57                 fg = 1;
58                 sum = 0;
59                 dfs(P(i, j));
60                 if (fg) lake.push(PP(sum, P(i, j)));
61             }
62     int ans = 0;
63     while (lake.size() != k) {
64         ans += lake.top().first;
65         dfs2(lake.top().second);
66         lake.pop();
67     }
68     cout << ans << endl;
69     for (int i = 1; i <= n; i++) {
70         for (int j = 1; j <= m; j++)
71             cout << map[i][j];
72         cout << endl;
73     }
74     return 0;
75 }