[CF1495C] Garden of the Sun

[CF1495C] Garden of the Sun - 构造

Description

太阳花田是一个 (n imes m) 的矩阵。X 的位置是空地，. 的位置是向日葵，Imakf 保证给出的矩阵满足所有 X 两两之间的切比雪夫距离大于 (1)（没有公共点）。请把一些 . 换成 X，使得所有的 X 四连通且不存在简单环（形成一棵树）。

Solution

总体想法是将 2,5,8,... 行全部涂黑，然后比如考虑 3,4 行，我们希望直接把第一列涂黑这样就连起来了，但是如果二者中有一个第二列已黑，这样就错了，但是这时候我们可以把第二列涂黑，也连起来了

注意最后一行需要特判一下

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 505;

char a[N][N];

int n, m;

void solve()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i] + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 'X')
                a[i][j] = 1;
            else
                a[i][j] = 0;
    if (n == 1)
    {
        for (int i = 1; i <= m; i++)
            cout << 'X';
        cout << endl;
        return;
    }
    // todo: main
    for (int i = 2; i <= n; i += 3)
    {
        for (int j = 1; j <= m; j++)
            a[i][j] = 1;
        char *b = a[i + 1];
        char *c = a[i + 2];
        if (i + 2 <= n)
            if (b[2] || c[2])
                b[2] = 1, c[2] = 1;
            else
                b[1] = 1, c[1] = 1;
    }
    if (n % 3 == 1)
    {
        for (int i = 1; i <= m; i++)
            if (a[n][i] && !a[n][i - 1] && !a[n][i + 1] && !a[n - 1][i + 1] && !a[n - 1][i - 1])
                a[n - 1][i] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j])
                a[i][j] = 'X';
            else
                a[i][j] = '.';
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << a[i][j];
        cout << endl;
    }
    for (int i = 1; i <= n + 2; i++)
        for (int j = 1; j <= m + 2; j++)
            a[i][j] = 0;
}

signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
        solve();
}