#include <bits/stdc++.h>
using namespace std;
const int N = 301;
int n, a[N][N], vis[N * N], belong[N * N], id, tot;
vector<int>ve[N * N];
bool match(int x) {
    for (int i = 0; i < ve[x].size(); i++) {
        int tmp = ve[x][i];

        if (vis[tmp] != id) {
            vis[tmp] = id;

            if (!belong[tmp] || match(belong[tmp])) {
                belong[tmp] = x;
                return true;
            }
        }
    }

    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
                if (i - 1 >= 1 && a[i - 1][j] == a[i][j])
                    ve[(i - 1)*n + j].push_back((i - 2)*n + j);

                if (i + 1 <= n && a[i + 1][j] == a[i][j])
                    ve[(i - 1)*n + j].push_back(i * n + j);

                if (j + 1 <= n && a[i][j + 1] == a[i][j])
                    ve[(i - 1)*n + j].push_back((i - 1)*n + j + 1);

                if (j - 1 >= 1 && a[i][j - 1] == a[i][j])
                    ve[(i - 1)*n + j].push_back((i - 1)*n + j - 1);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if ((i % 2 == 0 && j % 2 == 0) || (i % 2 == 1 && j % 2 == 1)) {
                id = (i - 1) * n + j;

                if (match((i - 1)*n + j))
                    ++tot;
            }
        }
    }

    cout << tot * 2;
    return 0;
}

棋盘最大覆盖问题题解

题目分析

在一个 $n \times n$ 的棋盘中，每个方格为颜色 0 或 1。要求用 $1 \times 2$ 的卡片覆盖棋盘，规则如下：

• 卡片必须覆盖两个相邻（上下或左右）的方格；
• 被覆盖的两个方格颜色必须相同；
• 卡片不能重叠。

目标是求最多能覆盖的方格总数。

算法思路

本题可转化为二分图最大匹配问题，核心思路如下：

1. 二分图构建：
   棋盘可视为类似国际象棋的“黑白格”结构，按坐标 $(i,j)$ 的奇偶性将方格分为两类：

   • 一类为“黑格”：满足 $(i \% 2 == 0 \land j \% 2 == 0) \lor (i \% 2 == 1 \land j \% 2 == 1)$（即 $i+j$ 为偶数）；
   • 另一类为“白格”：其余方格（即 $i+j$ 为奇数）。
     显然，相邻的方格必分属两类（黑格与白格），这构成了二分图的两个顶点集。

2. 边的定义：
   若两个相邻方格（黑格与白格）颜色相同，则在它们之间连一条边，表示这两个方格可被一张卡片覆盖。

3. 最大匹配与结果：
   二分图的最大匹配数对应最多可放置的卡片数（每个匹配对应一张卡片），因此最大覆盖方格数为最大匹配数 $\times 2$。

算法标签

• 二分图最大匹配
• 匈牙利算法
• 棋盘覆盖问题

代码解析

核心变量与函数

关键步骤

1. 棋盘输入：读取 $n$ 和 $n \times n$ 的颜色矩阵。

2. 二分图构建：
   遍历所有“黑格”（左部节点），对每个黑格 $(i,j)$，检查其上下左右相邻的“白格”（右部节点）：

   • 若相邻方格颜色与当前黑格相同，则在邻接表中添加边（左部节点 $\to$ 右部节点）。
     节点编号规则：方格 $(i,j)$ 对应编号为 $(i-1) \times n + j$（将二维坐标转为一维）。

3. 最大匹配计算：
   对每个左部节点（黑格），调用匈牙利算法的 $match$ 函数寻找匹配，累计最大匹配数 $tot$。

4. 结果输出：最大覆盖方格数为 $tot \times 2$。

匈牙利算法详解

$match(x)$ 函数通过深度优先搜索为左部节点 $x$ 寻找匹配：

• 遍历 $x$ 的所有邻接右部节点 $y$；
• 若 $y$ 未被当前轮访问（$vis[y] \neq id$），标记访问并尝试匹配：
  • 若 $y$ 未匹配（$belong[y] = 0$），则直接匹配 $x \to y$；
  • 若 $y$ 已匹配，尝试让其原匹配节点 $belong[y]$ 寻找新匹配，若成功则更新匹配为 $x \to y$。

时间复杂度分析

• 棋盘大小为 $n \times n$，总节点数为 $O(n^2)$；
• 每个节点的邻边数最多为 4（上下左右），总边数为 $O(n^2)$；
• 匈牙利算法的时间复杂度为 $O(VE)$（$V$ 为顶点数，$E$ 为边数），此处 $V = O(n^2)$，$E = O(n^2)$，故总时间复杂度为 $O(n^4)$。
  由于 $n \leq 300$，$n^4 \approx 8.1 \times 10^9$，但实际中因边数少且算法优化（如访问标记），可高效运行。

示例解析

以样例输入（5×5 棋盘）为例：

• 按黑白格划分后，同色相邻的方格构成二分图的边；
• 最大匹配数为 9，因此最多覆盖 $9 \times 2 = 18$ 个方格，与样例输出一致。

通过二分图最大匹配模型，将棋盘覆盖问题转化为经典图论问题，高效求解了最大覆盖方格数。