棋盘覆盖问题与二分图匹配算法解析

1. 棋盘覆盖问题解析

棋盘覆盖问题是一个经典的算法题目，它要求我们在一个部分格子被禁止放置的棋盘上，尽可能多地放置1×2大小的骨牌（可以水平或垂直放置），且骨牌之间不能重叠。这个问题看似简单，但背后蕴含着深刻的图论原理。

1.1 问题建模思路

解决这个问题的关键在于将棋盘问题转化为图论中的二分图匹配问题。我们可以将棋盘看作一个二分图：

• 将棋盘上的每个可用格子视为图中的一个顶点
• 如果两个格子相邻（上下或左右相邻），就在它们之间建立一条边
• 这样，棋盘就变成了一个二分图，其中我们可以将棋盘按照国际象棋棋盘的黑白染色方式分成两部分

这种转化之所以有效，是因为：

1. 每个骨牌覆盖两个相邻格子，对应图中的一条边
2. 不重叠的骨牌放置对应图中的一组没有公共顶点的边（匹配）
3. 最大数量的骨牌放置对应图中的最大匹配

1.2 二分图与匈牙利算法

匈牙利算法是解决二分图最大匹配问题的经典算法。它的核心思想是通过不断寻找增广路径来扩大当前的匹配。增广路径是指从一个未匹配点出发，经过未匹配边、匹配边交替进行，最终到达另一个未匹配点的路径。

算法流程：

1. 初始化所有顶点为未匹配状态
2. 对于每个未匹配的顶点，尝试找到一条增广路径
3. 如果找到增广路径，则反转路径上的匹配状态（未匹配边变为匹配边，匹配边变为未匹配边）
4. 这样每次找到增广路径都能使匹配数增加1

2. 代码实现详解

2.1 数据结构设计

cpp复制const int maxn = 10010;
int match[maxn], vis[maxn], ans, n, t;
bool in[110][110];
vector <int> v[maxn];

• match数组：记录每个右部顶点匹配的左部顶点编号
• vis数组：标记顶点是否被访问过，防止重复访问
• in数组：标记哪些格子是被禁止放置的
• v数组：邻接表，存储图的边关系

2.2 坐标压缩函数

cpp复制int change(int x, int y) {
    return (x - 1) * 100 + y;
}

这个函数将二维坐标(x,y)压缩成一个唯一的整数，方便我们处理。选择100作为基数是因为题目中N的最大值是1