[Kickstart Round H 2019 B. Diagonal Puzzle] 2-SAT/二染色

1. 题目链接

Kickstart Round H 2019 B. Diagonal Puzzle

2. 题目描述

有一个 $N\times N$ 的正方形棋盘，棋盘上每个位置要么是黑子，要么是白子。现在需要用最少的步数将白子全部编程黑子。

每一步你可以任意选择一条该正方形的对角线，然后将对角线上的所有棋子都翻转 (白变黑 or 黑变白)。

下面是 $3\times 3$ 正方形的10种对角线：

/..      ./.      ../      ...      ...
...      /..      ./.      ../      ...
...      ...      /..      ./.      ../


...      ...      \..      .\.      ..\
...      \..      .\.      ..\      ...
\..      .\.      ..\      ...      ...

3. 解题思路

对于 $N\times N$ 的正方形来说，共存在 $\mathbf{4N-2}$ 条对角线。然后，对于一条对角线，多次翻转是没有意义的（翻转 2 次跟翻转 0 次没有区别），就是说每条对角线只有两种状态：翻转、不翻转。

然后对于棋盘中的每一个位置，都存在 2 条对角线经过该位置：

• 当这个位置为白子时，这两条对角线的状态必须是互斥的；
• 当这个位置为黑子时，这两条对角线的状态必须是相同的。

这样，整个问题就是变成了对 对角线的2-SAT/二染色问题。而上述两种情况，可以看成染色的限制条件。

那我们对每个连通块进行 dfs 进行二染色，然后统计染色为 0、1 的节点个数。如果染色为 0 的节点个数较少，我们则翻转连通块中所有染色为 0 的节点；反之，则翻转染色为 1 的节点。

4. 参考代码

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

typedef long long ll;
typedef unsigned long long ull;

const long double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T> void umax(T& a, const T b) { a = max(a, b);  }
template<typename T> void umin(T& a, const T b) { a = min(a, b);  }

const int MAXN = 105;
int T, N, ans;
char s[MAXN];
vector<int> edge[4*MAXN];   // 4n-2
int flag[4*MAXN];
int pr[MAXN*4][MAXN*4];

/**
 * dfs 进行二染色
 * 路径保存在 path 里，染色结果存在 flag 里
 */
vector<int> path;
void dfs(int u, int f) {
    flag[u] = f;
    path.push_back(u);
    for(int& v : edge[u]) {
        if (flag[v] != -1 || pr[u][v] == -1) continue;
        if (pr[u][v] == 0) {
            dfs(v, f);
        } else {
            dfs(v, f ^ 1);
        }
    }
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-2.txt", "r", stdin);
#endif
    scanf("%d", &T);
    for(int cas = 1; cas <= T; ++cas) {
        scanf("%d", &N);
        for(int i = 0 ; i < 4*N-2; ++i) edge[i].clear(), flag[i] = -1;
        memset(pr, -1, sizeof(pr));
        for(int i = 0; i < N; ++i) {
            scanf("%s", s);
            for(int j = 0; j < N; ++j) {
                // 求对应的两条对角线编号
                int u = i + j, v = 3*N-2-i+j;
                edge[u].push_back(v);
                edge[v].push_back(u);
                if(s[j] == '#') {
                    pr[u][v] = pr[v][u] = 0;
                } else {
                    pr[u][v] = pr[v][u] = 1;
                }
            }
        }
        ans = 0;
        for(int i = 0; i < 4*N-2; ++i) {
            if(flag[i] != -1) continue;
            // flag[i] == 1， 表示翻转该对角线
            path.clear();
            dfs(i, 1);
            int cnt[2] = {0, 0};
            for(int& v : path) cnt[flag[v]] += 1;
            if(cnt[0] < cnt[1]) {
                for(int& v : path) flag[v] ^= 1;
            }
            ans += min(cnt[0], cnt[1]);
        }
        printf("Case #%d: %d\n", cas, ans);
    }
    return 0;
}