[CF1450C2] Errich-Tac-Toe

[CF1450C2] Errich-Tac-Toe - 构造

Description

给定一个网格，有的格子填了 X 或 O，要求不能有三个横着或者竖着的 X 或 O 相连，你可以把 X 改成 O，把 O 改成 X。构造一种方案，操作次数不超过 (k/3)。

Solution

沿用 easy 版本的思想，但需要考虑一些性质

我们只需要让 3 个相邻的有 2 个不同就可以了

一定存在某一类，其中的个数不少于总个数的 1/3，我们钦定这一类不变，修改其它两类

在其他两类中，由于钦定一类为 X 一类为 O，正反两种方案中，一定有一种的修改量不会超过总数的一半

为了省事，我们在实现时，对于每一个类，用 3 种模式符描述：0 表示不修改，O 表示强行修改成 O，X 表示强行修改成 X，然后枚举即可

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

#define int long long

bool calc(vector<string> a, char x, char y, char z)
{
    int cnt = 0, tot = 0;
    int n = a.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == 'X' || a[i][j] == 'O')
                ++tot;
            char t;
            if ((i + j) % 3 == 0)
                t = x;
            if ((i + j) % 3 == 1)
                t = y;
            if ((i + j) % 3 == 2)
                t = z;
            if (t == 'X')
            {
                if (a[i][j] == 'O')
                    a[i][j] = 'X', ++cnt;
            }
            if (t == 'O')
            {
                if (a[i][j] == 'X')
                    a[i][j] = 'O', ++cnt;
            }
        }
    }
    if (cnt <= tot / 3)
    {
        for (int i = 0; i < n; i++)
            cout << a[i] << endl;
        return true;
    }
    return false;
}

void solve()
{
    int n;
    cin >> n;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (calc(a, '0', 'X', 'O'))
        return;
    if (calc(a, '0', 'O', 'X'))
        return;
    if (calc(a, 'X', '0', 'O'))
        return;
    if (calc(a, 'X', 'O', '0'))
        return;
    if (calc(a, 'O', '0', 'X'))
        return;
    if (calc(a, 'O', 'X', '0'))
        return;
}

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