1. 从棋盘到图论一个经典问题的建模思路很多朋友第一次接触“棋盘游戏”这个题目时可能会有点懵棋盘游戏和二分图最大匹配有什么关系这其实是算法竞赛和面试中一个非常经典的建模问题它完美地展示了如何将一个看似复杂的实际问题抽象成一个清晰的图论模型并利用成熟的算法高效解决。简单来说问题通常是这样描述的在一个N行M列的棋盘上有些格子是障碍物不能放置棋子现在要在棋盘上放置尽可能多的“车”国际象棋中的Rook要求任意两个“车”不能在同一行或同一列除非中间有障碍物隔开。问最多能放多少个如果你直接去穷举所有放置方案那复杂度是指数级的棋盘稍微大点就算不动了。但如果你把棋盘的行和列看成图的两部分把可放置的格子看成连接行和列的边这个问题瞬间就变成了一个标准的二分图最大匹配问题。这个建模过程本身就是解决此类问题的核心技巧。今天我们就来彻底拆解这个“棋盘游戏”从问题理解、建模、算法实现到代码细节手把手带你走一遍。无论你是正在准备算法面试还是想深入理解二分图的应用这篇文章都会给你带来实实在在的收获。2. 问题本质剖析为什么是二分图最大匹配要理解这个建模我们得先抛开“棋盘”这个具象抓住问题的核心约束放置的棋子不能共享同一行或同一列。这个约束是不是很耳熟它和二分图匹配的定义有异曲同工之妙。在二分图中我们把所有顶点分成两个独立的集合X和Y。一个匹配就是从X到Y的一种配对关系要求每个顶点至多与另一集合中的一个顶点相连。映射到我们的棋盘问题集合X我们可以将所有“有效的行”视为一个集合。注意这里“有效的行”不是指物理行号而是指被障碍物分割开的、连续的可放置格子构成的“行连通块”。因为障碍物隔开了同一物理行所以被隔开的不同段之间互不影响。集合Y同样将所有“有效的列”视为另一个集合即被障碍物分割开的“列连通块”。边棋盘上的一个可放置格子(i, j)就对应着它所在的行连通块记为row_id[i][j]和列连通块记为col_id[i][j]之间的一条边。这样在棋盘上放置一个棋子就相当于在二分图中选择一条边匹配一条边。而“任意两个棋子不能同行同列”的约束正好对应了“匹配”的定义在同一个行连通块X集合顶点上只能选一条边放一个棋子在同一个列连通块Y集合顶点上也只能选一条边放一个棋子。我们的目标——放置尽可能多的棋子自然就转化成了在这个构建的二分图上寻找最大匹配。所以整个问题的解决流程就清晰了预处理棋盘给每个可放置的格子打上“行连通块ID”和“列连通块ID”的标签。根据这些ID构建二分图。在构建的二分图上跑一遍最大匹配算法如匈牙利算法得到的最大匹配数就是答案。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和mgraph[u]存储了与X集合顶点u相连的所有Y集合顶点。#include vector #include cstring using namespace std; const int MAXN 1005; // 根据题目最大规模调整 vectorint 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; }代码要点解析matchY[v] u这个数组是关键它记录了最终匹配的结果。matchY[v] 0表示顶点v还未被匹配。visited数组必须在每次为新的u寻找匹配前清空。它用于在单次DFS中标记Y集合的顶点是否被访问过防止在递归寻找增广路时陷入死循环。时间复杂度最坏情况下是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]; vectorint 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; }逐段解读与避坑指南数组大小MAX设为105是考虑到棋盘可能100*100而行/列连通块的数量最多不会超过格子数最坏情况每个格子都是独立块所以MAX*MAX是安全的。在实际比赛中要根据题目数据范围精确计算。编号逻辑行编号的循环是for i, for j列编号的循环是for j, for i。这是保证行方向、列方向连续性的关键顺序不能错。编号的连续性代码中row_cnt和col_cnt是全局递增的。注意在行扫描中换到新的一行时如果第一个格子是可放置的并且上一行对应位置不是障碍物延续下来的同一块我们的逻辑是每行独立扫描那么它就会得到一个新的row_cnt。这符合“行连通块”的定义。列扫描同理。建图去重理论上同一个(r, c)对可能由多个格子产生虽然在这个问题定义中不会因为一个行块和一个列块最多交于一个格子。但我们的建图方式是遍历所有格子并push_back如果存在重复边也不会影响匈牙利算法的正确性只是增加了不必要的边。如果追求极致效率可以使用set或建图后排序去重但通常没必要。匹配结果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的棋盘没有障碍物.. ..手动计算行连通块第一行一个块(id1)第二行一个块(id2)。列连通块第一列一个块(id1)第二列一个块(id2)。建图格子(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是行连通块数量最多KE是边数恰好为K。所以最坏是O(K^2)。考虑到K最大可能为NM也就是O((N*M)^2)。对于N,M 100这完全可行1e8操作量级现代计算机可接受。但如果N,M达到500K接近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算法作为你的进阶技能。
1. 从棋盘到图论一个经典问题的建模思路很多朋友第一次接触“棋盘游戏”这个题目时可能会有点懵棋盘游戏和二分图最大匹配有什么关系这其实是算法竞赛和面试中一个非常经典的建模问题它完美地展示了如何将一个看似复杂的实际问题抽象成一个清晰的图论模型并利用成熟的算法高效解决。简单来说问题通常是这样描述的在一个N行M列的棋盘上有些格子是障碍物不能放置棋子现在要在棋盘上放置尽可能多的“车”国际象棋中的Rook要求任意两个“车”不能在同一行或同一列除非中间有障碍物隔开。问最多能放多少个如果你直接去穷举所有放置方案那复杂度是指数级的棋盘稍微大点就算不动了。但如果你把棋盘的行和列看成图的两部分把可放置的格子看成连接行和列的边这个问题瞬间就变成了一个标准的二分图最大匹配问题。这个建模过程本身就是解决此类问题的核心技巧。今天我们就来彻底拆解这个“棋盘游戏”从问题理解、建模、算法实现到代码细节手把手带你走一遍。无论你是正在准备算法面试还是想深入理解二分图的应用这篇文章都会给你带来实实在在的收获。2. 问题本质剖析为什么是二分图最大匹配要理解这个建模我们得先抛开“棋盘”这个具象抓住问题的核心约束放置的棋子不能共享同一行或同一列。这个约束是不是很耳熟它和二分图匹配的定义有异曲同工之妙。在二分图中我们把所有顶点分成两个独立的集合X和Y。一个匹配就是从X到Y的一种配对关系要求每个顶点至多与另一集合中的一个顶点相连。映射到我们的棋盘问题集合X我们可以将所有“有效的行”视为一个集合。注意这里“有效的行”不是指物理行号而是指被障碍物分割开的、连续的可放置格子构成的“行连通块”。因为障碍物隔开了同一物理行所以被隔开的不同段之间互不影响。集合Y同样将所有“有效的列”视为另一个集合即被障碍物分割开的“列连通块”。边棋盘上的一个可放置格子(i, j)就对应着它所在的行连通块记为row_id[i][j]和列连通块记为col_id[i][j]之间的一条边。这样在棋盘上放置一个棋子就相当于在二分图中选择一条边匹配一条边。而“任意两个棋子不能同行同列”的约束正好对应了“匹配”的定义在同一个行连通块X集合顶点上只能选一条边放一个棋子在同一个列连通块Y集合顶点上也只能选一条边放一个棋子。我们的目标——放置尽可能多的棋子自然就转化成了在这个构建的二分图上寻找最大匹配。所以整个问题的解决流程就清晰了预处理棋盘给每个可放置的格子打上“行连通块ID”和“列连通块ID”的标签。根据这些ID构建二分图。在构建的二分图上跑一遍最大匹配算法如匈牙利算法得到的最大匹配数就是答案。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和mgraph[u]存储了与X集合顶点u相连的所有Y集合顶点。#include vector #include cstring using namespace std; const int MAXN 1005; // 根据题目最大规模调整 vectorint 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; }代码要点解析matchY[v] u这个数组是关键它记录了最终匹配的结果。matchY[v] 0表示顶点v还未被匹配。visited数组必须在每次为新的u寻找匹配前清空。它用于在单次DFS中标记Y集合的顶点是否被访问过防止在递归寻找增广路时陷入死循环。时间复杂度最坏情况下是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]; vectorint 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; }逐段解读与避坑指南数组大小MAX设为105是考虑到棋盘可能100*100而行/列连通块的数量最多不会超过格子数最坏情况每个格子都是独立块所以MAX*MAX是安全的。在实际比赛中要根据题目数据范围精确计算。编号逻辑行编号的循环是for i, for j列编号的循环是for j, for i。这是保证行方向、列方向连续性的关键顺序不能错。编号的连续性代码中row_cnt和col_cnt是全局递增的。注意在行扫描中换到新的一行时如果第一个格子是可放置的并且上一行对应位置不是障碍物延续下来的同一块我们的逻辑是每行独立扫描那么它就会得到一个新的row_cnt。这符合“行连通块”的定义。列扫描同理。建图去重理论上同一个(r, c)对可能由多个格子产生虽然在这个问题定义中不会因为一个行块和一个列块最多交于一个格子。但我们的建图方式是遍历所有格子并push_back如果存在重复边也不会影响匈牙利算法的正确性只是增加了不必要的边。如果追求极致效率可以使用set或建图后排序去重但通常没必要。匹配结果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的棋盘没有障碍物.. ..手动计算行连通块第一行一个块(id1)第二行一个块(id2)。列连通块第一列一个块(id1)第二列一个块(id2)。建图格子(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是行连通块数量最多KE是边数恰好为K。所以最坏是O(K^2)。考虑到K最大可能为NM也就是O((N*M)^2)。对于N,M 100这完全可行1e8操作量级现代计算机可接受。但如果N,M达到500K接近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算法作为你的进阶技能。
