Codeforces Round 928 (Div. 4) F. Vlad and Avoiding X

Vlad and Avoiding X

题目描述

弗拉迪斯拉夫有一个大小为 $\times 7$ 的网格，其中每个单元格的颜色都是黑色或白色。在一次操作中，他可以选择任意一个单元格并改变其颜色（黑色 $\leftrightarrow$ 白色）。

请找出最少需要多少次运算才能确保没有黑色单元格的对角线上的四个相邻单元格也是黑色的。

左图显示，最初有两个黑色单元格违反了条件。只要翻转一个单元格，网格就能正常工作。

输入描述

第一行输入包含一个整数 $t$ ( $\leq t \leq 200$ ) - 测试用例的数量。然后是测试用例的描述。

每个测试用例由 $7$ 行组成，每行包含 $7$ 个字符。每个字符都是 $\texttt{W}$ 或 $\texttt{B}$ ，分别表示白色或黑色单元格。

输出描述

对于每个测试用例，输出一个整数 - 为确保没有黑色单元格且所有四个对角线相邻单元格也是黑色所需的最少操作数。

样例输入

4
WWWWWWW
WWWWBBB
WWWWWBW
WWBBBBB
WWWBWWW
WWBBBWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
WBBBBBW
WBBBBBW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WWWWWWW
WBBBBBW
BBBBBBB
BBBBBBB
WWWWWWW
BBBBBBB
BBBBBBB
BBBBBBB

样例输出

原题

CF——传送门

代码

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);

char g[7][7];

struct node
{
    int x, y;
};

bool check(int valid_num) // 检查该种翻转方案是否可行
{
    for (int i = 1; i < 6; i++)
    {
        for (int j = 1; j < 6; j++)
        {
            if (valid_num != ((i + j) % 2)) // 不属于该板块的点就跳过
                continue;
            if (g[i][j] && g[i - 1][j - 1] && g[i - 1][j + 1] && g[i + 1][j - 1] && g[i + 1][j + 1]) // 一旦发现x图形，返回0，该方案不可行
                return 0;
        }
    }
    return 1;
}

bool dfs(vector<node> &v, int cnt_left, int idx, int valid_num) // v为对应板块的'B'所在的点的数组，cnt_left为剩下需要翻转的次数，idx为数组的索引，valid_num表示奇数板块还是偶数板块
{
    if (cnt_left == 0)
        return check(valid_num); // 翻转次数用完后，检查是否可行
    if (idx == v.size())         // idx遍历完数组仍未找到可行方案，返回0
        return 0;
    bool ok = 0;
    ok |= dfs(v, cnt_left, idx + 1, valid_num);     // 该点不翻转，递归下一个点
    g[v[idx].x][v[idx].y] ^= 1;                     // 翻转
    ok |= dfs(v, cnt_left - 1, idx + 1, valid_num); // 该点翻转，递归下一个点
    g[v[idx].x][v[idx].y] ^= 1;                     // 回溯
    return ok;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 7; i++)
        {
            for (int j = 0; j < 7; j++)
            {
                char c;
                cin >> c;
                g[i][j] = (c == 'B'); // 将'B'用1存储，便于操作，相对应的，0表示'W'
            }
        }
        // 将7X7的板块分为两个互不影响的板块
        vector<node> a, b;
        for (int i = 0; i < 7; i++)
        {
            for (int j = 0; j < 7; j++)
            {
                if (g[i][j])
                {
                    if ((i + j) % 2 == 0)
                    {
                        a.push_back({i, j}); // 加入偶数板块
                    }
                    else
                    {
                        b.push_back({i, j}); // 加入奇数板块
                    }
                }
            }
        }
        int ans = 0;
        // 最多只要翻转4个点即可令其不存在x图形
        for (int i = 0; i <= 4; i++)
        {
            if (dfs(a, i, 0, 0))
            {
                ans += i;
                break;
            }
        }
        for (int i = 0; i <= 4; i++)
        {
            if (dfs(b, i, 0, 1))
            {
                ans += i;
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}