题目翻译

给定 $7\times 7$ 的黑白网格，问至少改多少点才能使得不出现大小为 $3\times 3$ 的黑色 $\tt X$ 形。定义改一个点指改变这个点的颜色，黑变成白，白变成黑。

多测，$1\leq t\leq 200$。

题目思路

显然只需要黑色改白色。

一个不是很显然的结论是 $ans\leq 8$。

你考虑对于网格进行红绿染色（其实就是黑白染色，但是和题意重合了）。就是 $(1,1)$ 红色，$(1,2)$ 和 $(2,1)$ 绿色这样子交叉递推。显然红色与绿色的部分是可以分开计算的。

然后我们瞪眼法发现一个 $ans=8$ 的通解：染色 $(3,3),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4),(5,5)$。这也就告诉我们，$ans$ 上界为 $8$。其中红绿两部分各 $4$ 个。

但是这不一定能构造最优解。因为我在 test 2 的 case 16 WA 了。

但是这启发我们，因为答案很小，每个部分也都很少，我们可以直接暴力枚举具体是哪 $4$ 个格子被染白了。

时间复杂度是 $\mathcal O(\binom{25}{4}\times 25+\binom{24}{4}\times 24)$ 的。后面加的 $\times 25$ 之类的是用来 check 是否为合法的方案的。时间复杂度能这么写吗我不知道啊。

完整代码

写的很丑。

CF submission 247566445

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
const int n = 7;
const int m = 9;
const int dx[] = {3, 3, 3, 4, 4, 4, 5, 5, 5};
const int dy[] = {3, 4, 5, 3, 4, 5, 3, 4, 5};
char mp[10][10];
vector<pii> v[2];
bool ok(int x, int y) { return mp[x - 1][y - 1] == 'B' && mp[x - 1][y + 1] == 'B' && mp[x + 1][y - 1] == 'B' && mp[x + 1][y + 1] == 'B'; }
void change(pii a, char to) { mp[a.first][a.second] = to; }
int siz(int a, int b, int c, int d)
{
    set<int> s;
    s.insert(a);
    s.insert(b);
    s.insert(c);
    s.insert(d);
    return s.size();
}
int calc(vector<pii> &v)
{
    bool need = 0;
    for (pii p : v)
    {
        int x = p.first;
        int y = p.second;
        if (mp[x][y] == 'B')
            if (ok(x, y))
                need = 1;
    }
    if (!need)
        return 0;
    int ret = 8;
    for (int p1 = 0; p1 < v.size(); p1++)
    {
        for (int p2 = p1; p2 < v.size(); p2++)
        {
            for (int p3 = p2; p3 < v.size(); p3++)
            {
                for (int p4 = p3; p4 < v.size(); p4++)
                {
                    need = 1;
                    change(v[p1], 'W'), change(v[p2], 'W'), change(v[p3], 'W'), change(v[p4], 'W');
                    for (pii p : v)
                    {
                        int x = p.first;
                        int y = p.second;
                        if (mp[x][y] == 'B')
                            if (ok(x, y))
                                need = 0;
                    }
                    if (need)
                        chkmn(ret, siz(p1, p2, p3, p4));
                    change(v[p1], 'B'), change(v[p2], 'B'), change(v[p3], 'B'), change(v[p4], 'B');
                }
            }
        }
    }
    return ret;
}
void solve()
{
    v[0].clear(), v[1].clear();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> mp[i][j];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            if (mp[i][j] == 'B')
                v[(i & 1) ^ (j & 1)].push_back({i, j});
    }
    cout << calc(v[0]) + calc(v[1]) << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}