洛谷

CF

分析

发现在一个边长为 \(2\) 的联通块中，如果只有一个是*，就必须将其改变，然后 \(bfs\) 找就好了。

代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

queue <P> q;

int n, m;
int g[N][N];
char mp[N][N];

bool check(int x, int y) {
    return g[x][y] + g[x+1][y] + g[x][y+1] + g[x+1][y+1] == 3;
}

bool change(int x, int y) {
    if (g[x][y]) return false;
    if (check(x, y)) return true;
    if (x-1 > 0 && check(x-1, y)) return true;
    if (y-1 > 0 && check(x, y-1)) return true;
    if (x-1 > 0 && y-1 > 0 && check(x-1, y-1)) return true;
    return false;
}

void bfs() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (change(i, j)) {
                g[i][j] = 1;
                q.push(make_pair(i, j));
            }
    while (!q.empty()) {
        P k = q.front(); q.pop();
        for (int i = k.first - 1; i <= k.first + 1; ++i)
            for (int j = k.second - 1; j <= k.second + 1; ++j)
                if (i > 0 && j > 0 && i <= n && j <= m && change(i, j)) {
                    g[i][j] = 1;
                    q.push(make_pair(i, j));
                }
    }
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> mp[i][j];
            g[i][j] = (mp[i][j] == '.') ? 1 : 0;
        }
    bfs();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            if (g[i][j] == 1) putchar('.');
            else putchar('*');
            if (j == m) printf("\n");
        }
    return 0;
}