1. 从棋盘到图论：一个经典问题的建模思路

很多朋友第一次接触“棋盘游戏”这个题目时，可能会有点懵：棋盘游戏和二分图最大匹配有什么关系？这其实是算法竞赛和面试中一个非常经典的建模问题，它完美地展示了如何将一个看似复杂的实际问题，抽象成一个清晰的图论模型，并利用成熟的算法高效解决。简单来说，问题通常是这样描述的：在一个N行M列的棋盘上，有些格子是障碍物（不能放置棋子），现在要在棋盘上放置尽可能多的“车”（国际象棋中的Rook），要求任意两个“车”不能在同一行或同一列（除非中间有障碍物隔开）。问最多能放多少个？

如果你直接去穷举所有放置方案，那复杂度是指数级的，棋盘稍微大点就算不动了。但如果你把棋盘的行和列看成图的两部分，把可放置的格子看成连接行和列的边，这个问题瞬间就变成了一个标准的二分图最大匹配问题。这个建模过程本身，就是解决此类问题的核心技巧。今天，我们就来彻底拆解这个“棋盘游戏”，从问题理解、建模、算法实现到代码细节，手把手带你走一遍。无论你是正在准备算法面试，还是想深入理解二分图的应用，这篇文章都会给你带来实实在在的收获。

2. 问题本质剖析：为什么是二分图最大匹配？

要理解这个建模，我们得先抛开“棋盘”这个具象，抓住问题的核心约束：放置的棋子不能共享同一行或同一列。这个约束是不是很耳熟？它和二分图匹配的定义有异曲同工之妙。

在二分图中，我们把所有顶点分成两个独立的集合X和Y。一个匹配，就是从X到Y的一种配对关系，要求每个顶点至多与另一集合中的一个顶点相连。映射到我们的棋盘问题：

• 集合X：我们可以将所有“有效的行”视为一个集合。注意，这里“有效的行”不是指物理行号，而是指被障碍物分割开的、连续的可放置格子构成的“行连通块”。因为障碍物隔开了同一物理行，所以被隔开的不同段之间互不影响。
• 集合Y：同样，将所有“有效的列”视为另一个集合，即被障碍物分割开的“列连通块”。
• 边：棋盘上的一个可放置格子(i, j)，就对应着它所在的行连通块（记为row_id[i][j]）和列连通块（记为col_id[i][j]）之间的一条边。

这样，在棋盘上放置一个棋子，就相当于在二分图中选择一条边（匹配一条边）。而“任意两个棋子不能同行同列”的约束，正好对应了“匹配”的定义：在同一个行连通块（X集合顶点）上只能选一条边（放一个棋子），在同一个列连通块（Y集合顶点）上也只能选一条边（放一个棋子）。我们的目标——放置尽可能多的棋子，自然就转化成了在这个构建的二分图上寻找最大匹配。

所以，整个问题的解决流程就清晰了：

1. 预处理棋盘，给每个可放置的格子打上“行连通块ID”和“列连通块ID”的标签。
2. 根据这些ID，构建二分图。
3. 在构建的二分图上跑一遍最大匹配算法（如匈牙利算法），得到的最大匹配数，就是答案。

3. 关键步骤拆解：连通块编号与建图

理论懂了，接下来就是实操。整个过程最核心、也最容易出错的就是第一步：如何正确地给棋盘上的每个可放置格子进行“行连通块”和“列连通块”的编号。

3.1 行连通块的编号

我们以行为主序遍历棋盘。对于每一行，我们从左到右扫描。

• 初始化一个行块ID计数器，比如从1开始。
• 遇到一个可放置的格子（非障碍物），我们就给它赋予当前的行块ID。
• 继续向右扫描，如果下一个格子也是可放置的，那么它和上一个格子属于同一个行连通块，ID不变。
• 如果遇到障碍物，或者到了行尾，那么当前的行连通块就结束了。当再次遇到可放置格子时（可能在同一行，但被障碍物隔开；也可能在下一行），我们就将行块ID计数器加1，开始一个新的行连通块。

这样一趟扫描下来，棋盘上每个可放置的格子都有一个唯一的row_id。关键点在于：被障碍物隔开的同一物理行上的两段可放置区域，它们的row_id是不同的。这保证了后续匹配时，它们被视为不同的“行资源”。

3.2 列连通块的编号

列连通块的编号逻辑完全对称，只是扫描方向变了。我们以列为主序遍历棋盘，从上到下扫描每一列。

• 初始化一个列块ID计数器，也从1开始（注意，这里的ID和行块ID是独立的命名空间）。
• 遇到可放置格子，赋予当前的列块ID。
• 向下扫描，连续可放置则ID不变，遇到障碍物或列尾则列块结束，ID计数器加1。

经过行列两次扫描，我们得到了两个矩阵（或二维数组）row_id和col_id，它们和棋盘等大，其中非障碍物的格子存储着对应的连通块编号。

3.3 构建二分图

有了row_id和col_id，建图就非常简单了。我们遍历所有可放置的格子(i, j)。

• 对于这个格子，它的行块编号是r = row_id[i][j]，列块编号是c = col_id[i][j]。
• 这就在二分图中添加了一条从r到c的边。

这里有一个非常重要的细节：行块编号和列块编号是两套独立的体系。在最终的二分图中，X集合的顶点范围是[1, max_row_id]，Y集合的顶点范围是[1, max_col_id]。我们需要分别记录最大的行块ID和列块ID，以便初始化图结构。

注意：在实际存储时，通常使用邻接表。因为每个格子最多贡献一条边，所以邻接表的大小是可控的。graph[r]这个列表里，存储的就是所有与行块r相连的列块c。

4. 算法核心：匈牙利算法实现与优化

图建好了，接下来就是求最大匹配。最经典、最常用的算法就是匈牙利算法（Hungarian Algorithm）。它的核心思想是“腾挪”：尝试为当前X集合的顶点u寻找匹配，如果它心仪的Y集合顶点v已经被别人（u‘）匹配了，就去递归地问u‘：“你能不能换一个匹配对象？”，如果u‘能换成功，那么u就可以匹配v；如果u‘换不成功，那么u就只能放弃v，尝试下一个选择。

4.1 标准DFS实现

下面给出一个非常清晰的标准DFS实现模板。我们假设二分图的两个集合顶点数分别为n和m，graph[u]存储了与X集合顶点u相连的所有Y集合顶点。

#include <vector> #include <cstring> using namespace std; const int MAXN = 1005; // 根据题目最大规模调整 vector<int> graph[MAXN]; // 邻接表 int matchY[MAXN]; // 记录Y集合中每个顶点匹配的X顶点编号，未匹配则为0 bool visited[MAXN]; // DFS访问标记，防止重复访问 // DFS函数：尝试为X集合的顶点u寻找增广路 bool dfs(int u) { for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; // 如果v未被匹配，或者已经匹配但可以为它的原配找到新的匹配 if (matchY[v] == 0 || dfs(matchY[v])) { matchY[v] = u; // 匹配成功 return true; } } } return false; // 尝试了所有v，都找不到增广路 } // 主函数：计算最大匹配 int hungarian(int n) { // n是X集合的顶点数 int matchCount = 0; memset(matchY, 0, sizeof(matchY)); for (int u = 1; u <= n; ++u) { memset(visited, false, sizeof(visited)); if (dfs(u)) { matchCount++; } } return matchCount; }

代码要点解析：

1. matchY[v] = u：这个数组是关键，它记录了最终匹配的结果。matchY[v] == 0表示顶点v还未被匹配。
2. visited数组：必须在每次为新的u寻找匹配前清空。它用于在单次DFS中标记Y集合的顶点是否被访问过，防止在递归寻找增广路时陷入死循环。
3. 时间复杂度：最坏情况下是O(V*E)，其中V是顶点数，E是边数。对于棋盘游戏这类问题，顶点数通常是棋盘规模，边数最多是棋盘格子数，因此完全可行。

4.2 一个常见的优化与误区

你可能见过一些代码在DFS内部这样写：

if (matchY[v] == -1 || dfs(matchY[v])) { ... }

然后初始化matchY为-1。这和我们用0初始化在逻辑上是等价的，因为顶点编号通常从1开始。但使用0初始化更安全，因为它避免了“-1”可能作为一个有效顶点编号（如果编号从0开始）带来的混淆。我个人的习惯是坚持顶点从1开始编号，并用0表示“未匹配”，这样代码最清晰。

另一个实战心得：在棋盘游戏这类问题中，二分图通常比较稠密（每个行连通块可能连接多个列连通块）。虽然匈牙利算法能工作，但在一些极端大的棋盘（比如1000*1000且障碍很少）上可能会面临挑战。这时，使用Hopcroft-Karp算法（基于BFS的多路增广）可以将时间复杂度优化到O(sqrt(V)*E)，是更优的选择。不过对于绝大多数竞赛和面试题，标准的匈牙利算法已经足够。

5. 完整代码实现与逐行解读

理论、建模、算法都齐了，现在我们把它们组装起来。下面是一个针对典型问题输入格式的完整C++实现。假设输入格式为：第一行两个整数N, M表示棋盘大小，接下来一个N*M的字符矩阵，.表示可放置格子，#表示障碍物。

#include <iostream> #include <vector> #include <cstring> using namespace std; const int MAX = 105; // 假设棋盘最大为100*100，连通块数量不会超过格子数 char board[MAX][MAX]; int row_id[MAX][MAX], col_id[MAX][MAX]; vector<int> graph[MAX * MAX]; // 图，行连通块作为左部顶点 int match[MAX * MAX]; // match[col_id] = row_id bool visited[MAX * MAX]; int row_cnt = 0, col_cnt = 0; // 匈牙利算法DFS bool dfs(int u) { for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; if (match[v] == 0 || dfs(match[v])) { match[v] = u; return true; } } } return false; } int main() { int N, M; cin >> N >> M; for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { cin >> board[i][j]; } } // Step 1: 给每个可放置格子进行行连通块编号 for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (board[i][j] == '.') { if (j == 0 || board[i][j-1] == '#') { // 当前格子是行首，或者左边是障碍物，开启一个新的行块 row_cnt++; } row_id[i][j] = row_cnt; } } // 换行时，行块编号可以连续，也可以不连续，但为了清晰，这里遇到障碍物后下一行自然就是新块开始。 // 实际上，我们的编号逻辑已经保证了连续性。 } // Step 2: 给每个可放置格子进行列连通块编号 for (int j = 0; j < M; ++j) { for (int i = 0; i < N; ++i) { if (board[i][j] == '.') { if (i == 0 || board[i-1][j] == '#') { // 当前格子是列首，或者上边是障碍物，开启一个新的列块 col_cnt++; } col_id[i][j] = col_cnt; } } } // Step 3: 建图 for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { if (board[i][j] == '.') { int r = row_id[i][j]; int c = col_id[i][j]; graph[r].push_back(c); } } } // Step 4: 匈牙利算法求最大匹配 int ans = 0; memset(match, 0, sizeof(match)); for (int u = 1; u <= row_cnt; ++u) { memset(visited, false, sizeof(visited)); if (dfs(u)) { ans++; } } cout << ans << endl; return 0; }

逐段解读与避坑指南：

1. 数组大小：MAX设为105是考虑到棋盘可能100*100，而行/列连通块的数量最多不会超过格子数（最坏情况每个格子都是独立块），所以MAX*MAX是安全的。在实际比赛中，要根据题目数据范围精确计算。
2. 编号逻辑：行编号的循环是for i, for j；列编号的循环是for j, for i。这是保证行方向、列方向连续性的关键，顺序不能错。
3. 编号的连续性：代码中row_cnt和col_cnt是全局递增的。注意在行扫描中，换到新的一行时，如果第一个格子是可放置的，并且上一行对应位置不是障碍物延续下来的同一块（我们的逻辑是每行独立扫描），那么它就会得到一个新的row_cnt。这符合“行连通块”的定义。列扫描同理。
4. 建图去重：理论上，同一个(r, c)对可能由多个格子产生（虽然在这个问题定义中不会，因为一个行块和一个列块最多交于一个格子）。但我们的建图方式是遍历所有格子并push_back，如果存在重复边，也不会影响匈牙利算法的正确性，只是增加了不必要的边。如果追求极致效率，可以使用set或建图后排序去重，但通常没必要。
5. 匹配结果：ans就是最大匹配数，也就是最多能放置的棋子数。match数组存储了具体的匹配方案（哪个列块匹配了哪个行块），但本题通常只要求数量。

6. 变种与扩展思考

掌握了基础模型，我们来看看这个问题的几个常见变种和扩展，这能帮你真正吃透这个建模思想。

6.1 变种一：放置“皇后”而不是“车”

如果问题变成放置“皇后”（Queen），规则是任意两个皇后不能在同一行、同一列、同一对角线。这还能用二分图匹配吗？答案是不能直接套用。因为“不能在同一对角线”这个约束破坏了行、列资源的独立性。一个格子会同时影响它的行、列和两条对角线。这通常需要更复杂的算法，如搜索（DFS+剪枝）或转化为精确覆盖问题（Dancing Links）。

6.2 变种二：有权值的棋盘游戏

如果每个可放置格子有一个权值（比如收益），我们要在满足“车”的规则下，最大化总收益。这就从最大匹配变成了最大权匹配。对于二分图的最大权匹配，有经典的KM算法（Kuhn-Munkres算法）。KM算法比匈牙利算法复杂，但核心思想也是通过顶标和相等子图来寻找最优匹配。

6.3 扩展思考：建模的通用性

“棋盘游戏”的建模思想非常强大。其核心在于识别出问题中“两个互斥的约束维度”，并将其抽象为二分图的两部。类似的例子还有很多：

• 任务分配：n个工人，m个任务，每个工人只能做某些任务，一个任务只能由一个工人做。工人和任务就是二分图的两部。
• 课堂安排：n个老师，m个班级，每个老师只能教某些班级，一个班级同一时间只能由一个老师上课。老师和班级时间就是两部。
• 网络流量：在某些简化模型中，源点和汇点可以看作两部。

当你遇到一个看似复杂的问题时，不妨问问自己：这个问题中，是否存在两种类型的对象，它们之间的配对受到“一一对应”或“互斥”的约束？如果有，那么二分图匹配很可能就是你的解题钥匙。

7. 调试与常见错误排查

即使理解了算法，自己实现时也难免出错。下面分享几个我调试此类题目时积累的经验。

7.1 错误1：答案偏小

这是最常见的问题。可能的原因有：

• 建图错误：行连通块或列连通块编号逻辑有误。调试方法：打印出整个row_id和col_id矩阵，对照棋盘，肉眼检查每个可放置格子的行列编号是否正确。确保被障碍物隔开的区域编号不同，连续区域编号相同。
• 二分图顶点范围弄错：在调用匈牙利算法时，遍历的顶点范围应该是[1, row_cnt]，而不是棋盘的行数N。如果你错误地遍历了N，那么很多graph[u]可能是空的，导致匹配数减少。
• 数组越界：graph、match、visited数组的大小开小了。行块和列块的数量最多可能达到N*M（每个格子都是孤立块），所以数组大小要开MAXN * MAXM级别，而不是MAXN。

7.2 错误2：答案偏大或程序死循环

这通常发生在匈牙利算法的DFS实现中。

• visited数组未重置：这是最经典的错误。必须为每个新的左部顶点u单独重置visited数组。因为visited标记的是在当前这轮增广路搜索中，哪些右部顶点已经被尝试过，不能重复访问。如果不重置，会错误地剪枝，导致找不到本应存在的增广路，有时也可能导致递归逻辑混乱。
• 递归栈溢出：如果棋盘很大，建的图很深，DFS递归可能导致栈溢出。解决方案有两种：一是改用迭代形式的DFS（手动维护栈），二是使用BFS版本的匈牙利算法（即Hopcroft-Karp算法）。对于大多数OJ题目，递归深度在1000以内是安全的，但要注意检查。

7.3 一个实用的调试技巧

当你不确定算法是否正确时，可以尝试构造一个极小规模的测试用例，然后手动模拟算法的执行过程。 例如，一个2x2的棋盘，没有障碍物：

.. ..

手动计算：行连通块，第一行一个块(id=1)，第二行一个块(id=2)。列连通块，第一列一个块(id=1)，第二列一个块(id=2)。建图：格子(0,0)连接(1,1)，(0,1)连接(1,2)，(1,0)连接(2,1)，(1,1)连接(2,2)。然后手动跑匈牙利算法，应该得到最大匹配为2。如果得到1或0，那就肯定有问题。

再比如，一个带障碍物的：

.# ..

手动推导一下，再和程序输出对比。这种小数据调试法，对于定位建图阶段的逻辑错误非常有效。

8. 性能分析与算法选择

最后，我们来聊聊性能。对于棋盘游戏，假设棋盘大小为N x M，可放置格子数为K。

• 时间复杂度：
  • 连通块编号：需要扫描棋盘两次，O(N*M)。
  • 建图：遍历所有K个可放置格子，O(K)。
  • 匈牙利算法：最坏O(VE)。这里V是行连通块数量（最多K），E是边数（恰好为K）。所以最坏是O(K^2)。考虑到K最大可能为NM，也就是O((N*M)^2)。对于N,M <= 100，这完全可行（1e8操作量级，现代计算机可接受）。但如果N,M达到500，K接近25万，O(K^2)就可能超时。
• 空间复杂度：主要是存储row_id,col_id矩阵(O(N*M))和邻接表(O(K))。

何时需要更优算法？当N, M达到200以上，并且障碍物很少（K很大）时，就需要考虑Hopcroft-Karp算法了。它的时间复杂度是O(sqrt(V)*E)，在上述大规模稀疏二分图上优势明显。它的思想是通过BFS一次性找到多条不相交的增广路，然后用DFS沿这些路径增广。实现比匈牙利算法稍复杂，但模板化后也很好用。

对于面试和笔试，掌握标准的匈牙利算法和建模思想已经足够应对绝大多数情况。但在一些在线编程竞赛中，面对大数据规模，Hopcroft-Karp算法是你的必备武器。我的建议是：先熟练掌握匈牙利算法，彻底理解其原理和实现。当你能轻松解决中等规模问题时，再去学习和实现Hopcroft-Karp算法，作为你的进阶技能。