http://codeforces.com/contest/723/problem/D
这题是只能把小河填了，题目那里有写，其实如果读懂题这题是挺简单的，预处理出每一块的大小，排好序，从小到大填就行了。
以前找这些块的个数用的是dfs。现在这次用并查集做下。
首先要解决的是，二维坐标怎么并查集，以前的并查集都是一维的，现在是两个参数，那么就考虑离散，每对应一个点，离散到一个独特的一维数值即可。我用的公式的50 * x + y。这样得到的数值是唯一的。所以可以快乐地并查集了。
那么遇到一个'.'，我们需要它和其他合并，思路就是观察其上面和左边是否存在'.'，如果存在，就合并到左边（上面），没有，那就是自己一个块了。
有顺序的，检查完上面，合并完（现在爸爸是上面那个），还要检查左边，如果有，左边的就要合并过来。这样爸爸就只是上面那个了。
为什么要这样做呢？因为考虑下这个
***.**
*. ..**
枚举到加粗那个的时候，如果你只向左合并，则遗漏了上面那个，向上合并，又会使得左边的被算作不同的块。GG
所以是需要两边判断，同时合并的。注意合并的方向是固定的，需要及时选择那个是爸爸
然后就是排序删除了，每个点的爸爸是固定的，用个标记数组标记下删除了那个爸爸，输出的时候对应一下 就好
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = * ;
char str[ + ][ + ];
int fa[maxn];
LL size[maxn];
int calc(int x, int y) {
return * x + y;
}
int find(int x) {
if (fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[y] = x;
size[x] += size[y];
}
}
int del[maxn];
struct node {
LL size;
int FA;
bool operator < (const struct node &rhs) const {
return size < rhs.size;
}
node(LL aa, int bb) : size(aa), FA(bb) {}
};
multiset<struct node>ss;
bool used[maxn];
void work() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= n; ++i) {
scanf("%s", str[i] + );
}
for (int i = ; i <= maxn - ; ++i) {
size[i] = ;
fa[i] = i;
}
for (int i = ; i <= n; ++i) {
size[calc(i, )] = inf;
size[calc(i, m)] = inf;
}
for (int i = ; i <= m; ++i) {
size[calc(, i)] = inf;
size[calc(n, i)] = inf;
}
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
if (str[i][j] == '.') {
if (str[i - ][j] == '.' && i - >= ) {
merge(calc(i - , j), calc(i, j));
}
if (str[i][j - ] == '.' && j - >= ) merge(calc(i, j), calc(i, j - ));
}
}
}
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
if (str[i][j] == '*') continue;
int FA = find(calc(i, j));
if (used[FA]) continue;
if (size[FA] >= inf) continue;
ss.insert(node(size[FA], FA));
used[FA] = ;
}
}
multiset<struct node> :: iterator it = ss.begin();
int cut = ss.size() - k;
int ans = ;
while (cut--) {
del[it->FA] = ;
ans += size[it->FA];
it++;
}
printf("%d\n", ans);
for (int i = ; i <= n; ++i) {
for (int j = ; j <= m; ++j) {
int FA = find(calc(i, j));
if (del[FA]) {
printf("*");
} else printf("%c", str[i][j]);
}
printf("\n");
}
} int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
work();
return ;
}