C++11(clang++ 3.9) 解法, 执行用时: 124ms, 内存消耗: 66140K, 提交时间: 2019-03-16 11:42:06

#include<bits/stdc++.h>
#define LL long long
LL in() {
    char ch; LL x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
const int maxn = 1050;
const int inf = 0x7fffffff;
int bel[maxn][maxn], n, m, mp[maxn][maxn], num, siz[maxn * maxn], cnt[maxn * maxn];
int up[maxn * maxn], bj[maxn * maxn], ls, fa[maxn * maxn], must[maxn * maxn];
std::pair<int, int> spe[maxn * maxn];
char sss[maxn];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int rx[] = {1, -1, 0, 0};
int ry[] = {0, 0, 1, -1};
bool vis[maxn][maxn], flag, have;
std::set<int> v;
void dfs(int x, int y, int id) {
    siz[id]++;
    up[id] = std::min(up[id], x);
    bel[x][y] = id;
    vis[x][y] = true;
    for(int i = 0; i < 8; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && !vis[xx][yy] && mp[xx][yy]) dfs(xx, yy, id);
    }
}
void expand(int x, int y) {
    if(x == 1 || x == n || y == 1 || y == m) flag = true;
    vis[x][y] = true;
    for(int i = 0; i < 4; i++) {
        int xx = x + rx[i];
        int yy = y + ry[i];
        if(xx >= 1 && yy >= 1 && xx <= n && yy <= m) {
            if(mp[xx][yy]) v.insert(bel[xx][yy]);
            if(!mp[xx][yy] && !vis[xx][yy]) expand(xx, yy);
        }
    }
}
void init(int x, int y) {
#ifdef olinr
    printf("init %d %d\n", x, y);
#endif
    ls++;
    vis[x][y] = true;
    for(int i = 0; i < 4; i++) {
        int xx = x + rx[i];
        int yy = y + ry[i];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m) {
#ifdef olinr
            printf("in");
#endif
            if(!mp[xx][yy] && !vis[xx][yy]) have = true;
#ifdef olinr
            if(mp[xx][yy]) printf("!");
            if(!vis[xx][yy]) printf("$");
#endif
            if(mp[xx][yy] && !vis[xx][yy]) init(xx, yy);
        }
    }
}


void work(int x, int y) {
    v.clear();
    flag = false;
    have = false;
    ls = 0;
    expand(x, y);
    if(flag) {
#ifdef olinr
        //搜索到边界一定不是细胞质
    printf("break at 1\n");
#endif
        return;
    }
    if(v.size() != 2) {
        //一个膜里面一大堆不知道什么玩意
        int pos = 0, mx = inf;
        for(std::set<int>::iterator it = v.begin(); it != v.end(); it++)
            if(mx > up[*it]) mx = up[*it], pos = *it;
        //这个膜肯定没用了
        bj[pos] = true, cnt[pos] += v.size() - 1, must[pos] = true;
        for(std::set<int>::iterator it = v.begin(); it != v.end(); it++)
            if(*it != pos) fa[*it] = pos;
#ifdef olinr
        printf("vis: ");
        for(std::set<int>::iterator it = v.begin(); it != v.end(); it++) printf("%d ", *it);
        puts("");
        printf("break at 2\n");
#endif
        return;
    }
    std::set<int>::iterator it = v.begin();
    int aa = *it;
    it++;
    int bb = *it; 
    if(up[aa] > up[bb]) std::swap(aa, bb);
    if(bj[aa]) {
#ifdef olinr
        printf("break at 3\n");
#endif
        //已经用过了，就是两个粘在一起的细胞，然而在本题是不合法的
        must[aa] = true;
        return;
    }
    init(spe[bb].first, spe[bb].second);
    if(have) {
        //细胞核里有TM细胞质！！！我去
        must[aa] = true;
#ifdef olilnr
        printf("break at 4\n");
#endif
        return;
    }
    if(ls != siz[bb]) {
        //因为搜井号联通块是8联通的，这里要4联通搜一下，看是不是完整
#ifdef olinr
        printf("%d %d\n", ls, siz[bb]), printf("break at 5\n");
#endif
        must[aa] = true;
        return;
    }
    fa[aa] = 0, fa[bb] = aa;
    cnt[aa]++;
}
//must：是否一定不合法，bj是否曾经被作为细胞膜，fa，细胞核属于哪个细胞膜， cnt，作为细胞膜的次数
int main() {
    n = in(), m = in();
    for(int i = 1; i <= n; i++) {
        scanf("%s", sss);
        for(int j = 1; j <= m; j++)
            mp[i][j] = sss[j - 1] == '#';
    }
    //处理井号联通块
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(mp[i][j] && !vis[i][j]) {
                num++;
                up[num] = inf;
                spe[num] = std::make_pair(i, j);
                dfs(i, j, num);
#ifdef olinr
                printf("id: %d, siz = %d\n", num, siz[num]);
#endif
            }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            vis[i][j] = 0;
    //对于每个点的联通块，处理
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!mp[i][j] && !vis[i][j]) {
#ifdef olinr
                printf("now dfs %d %d\n", i, j);
#endif
                work(i, j);
            }
    int ans = 0;
    for(int i = 1; i <= num; i++) {
        bj[i] = false;
        if(!must[i] && !fa[i] && cnt[i] == 1) ans++, bj[i] = true;
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(!mp[i][j]) putchar('.');
            else {
                if(bj[bel[i][j]] || bj[fa[bel[i][j]]]) putchar('#');
                else putchar('.');
            }
        }
        puts("");
    }
    return 0;
}