看到HDU1198的标签是“模拟并查集”先给一个结论这道题真正卡人的地方不是并查集而是“模拟”那一半——更准确地说是怎么把11种水管的开口方向用程序语言表达清楚。题目叫Farm Irrigation说的是m行n列的农田里每块地埋着一种形状的水管水管和相邻地块的水管如果开口能对上就属于同一套灌溉网络。最后问整个农田一共有几套独立的灌溉区域。我刚学并查集那会儿做这题第一反应是“这不就是DFS数连通块嘛”确实Flood Fill也能过。但既然标签挂的是“模拟并查集”那就有必要把两个环节拆开模拟负责判断“能不能接上”并查集负责“接上之后合并成一组”。这个组合才是这题最值得学的地方。适合刚学完并查集、想找一道能练建模能力的题的人也适合之前用递归搜索写过但想换一种解法的同学。1. 问题本质一块农田就是一张网格图1.1 题目到底在问什么输入是两个整数m和n然后是一个m行n列的字符矩阵每个字符是A到K中的一种。字符代表不同形状的水管比如A是左上弯管B是右上弯管E是竖直管F是水平管K是十字四通管。这11种类型就是一张“零件表”。两块相邻地里的水管能不能连通要看接触面上是不是“开口对开口”。比如第i行第j列的地块向右有开口而它右边那块地向左有开口那这两块就能接上属于同一个灌溉系统。任务就是把所有能直接或间接连通的格子合并起来最后数一数有多少个独立集。换句话说把每个格子看成一个节点把“相邻且开口对接”看成一条无向边问题就变成——给定一个最多50×50的网格图求连通分量个数。这是标准的图论问题只是题目包装在“农田灌溉”里。1.2 连通块计数不是路径计数有些同学看到“水管”两个字第一反应是去模拟水怎么流动甚至想求最长路径这就偏了。这题不关心水从哪个口进、从哪个口出也不关心一条管路里具体怎么拐弯它只关心“哪几个格子最终被连成了一片”。举个例子一个2×2网格里四个格子都是K型四通管那四块地全部互相连通答案就是一个灌溉区域。这时候根本没有必要去模拟水分子怎么走只需要判断四块地是不是在同一个集合里。理解这一点很重要。一旦把“连通块计数”从“路径模拟”里摘出来思路就立刻清晰了模拟只负责判断相邻两格是否相通剩下的交给并查集。1.3 “模拟”和“并查集”各负责哪一半环节做的事对应代码模拟部分判断两个相邻地块的开口是否对接查当前管道方向、查邻居管道方向做与运算并查集部分如果可以对接把两个格子合并到同一个集合一维编号、并查集合并统计部分数有多少个集合根节点数fa[i] i的个数或者维护merge成功的次数这两部分完全解耦模拟只管“能不能连”并查集只管“要不要合并”。模拟的结果就是一个布尔值真则合并假则跳过。这种“规则判断集合合并”的模式在很多网格类题目里都能见到HDU1198只是包装得比较可爱而已。2. 管道建模用四个布尔位代替一长串if-else2.1 方向布尔组的设计写这一步最容易翻车的地方是看到一个字符就写一长串switch-case。比如“如果当前是A那就判断它上面有没有开口、左面有没有开口如果是B就判断上面和右面……”这样写不是不能过但代码又臭又长而且一不留神就漏掉某个方向调试起来想死的心都有。正确的做法是把每种管道建模成四个方向的布尔值。一个格子朝上、下、左、右是否开口用4个int或者bool表示1代表有开口0代表没有。这样就把“一个字符”转化成了“一个长度为4的数组”判断起来干净利落// 顺序固定为上、下、左、右 const int pipe[11][4] { {1, 0, 1, 0}, // A 左上弯管 {1, 0, 0, 1}, // B 右上弯管 {0, 1, 1, 0}, // C 左下弯管 {0, 1, 0, 1}, // D 右下弯管 {1, 1, 0, 0}, // E 竖直管 {0, 0, 1, 1}, // F 水平管 {1, 0, 1, 1}, // G 上、左、右三通 {0, 1, 1, 1}, // H 下、左、右三通 {1, 1, 1, 0}, // I 上、下、左三通 {1, 1, 0, 1}, // J 上、下、右三通 {1, 1, 1, 1} // K 四通 };数组的下标顺序我固定成“上、下、左、右”这样后面判断的时候只要记住pipe[type][0]是上pipe[type][1]是下pipe[type][2]是左pipe[type][3]是右。2.2 11种管道方向对照表如果你手头没有原题图可以把这张表当成“管道字典”管道向上开口向下开口向左开口向右开口A有无有无B有无无有C无有有无D无有无有E有有无无F无无有有G有无有有H无有有有I有有有无J有有无有K有有有有写代码之前最好把这个表在纸上画一遍尤其注意C和D、G和H很容易搞混。C是左下弯D是右下弯开口方向是镜像的G没有下开口H没有上开口。我当时就是因为把C和D记反样例死活过不去最后打印方向表才定位到错误。2.3 为什么只检查右邻居和下邻居相邻判断有两种写法写四个方向全都检查一遍或者只检查右边和下边。大部分题解用的是后者我建议你也用后者。理由很简单网格里每一对相邻格子之间的关系在按行从上到下、按列从左到右遍历时一定会被“左边那个格子”或者“上边那个格子”检查到一次。比如格子(i, j)和它左边的格子(i, j-1)在遍历到(i, j-1)时会去检查右边那时候这一对就已经判断过了等轮到(i, j)时完全没必要再回头看一眼左边。同理和上边邻居的关系在遍历到上边那一行时已经处理过了。所以主循环里只需要看两个方向(i, j)和(i, j1)当前格向右开口且右侧格向左开口(i, j)和(i1, j)当前格向下开口且下方格向上开口这样做还有一个好处边界判断只关心“有没有右邻居”和“有没有下邻居”不会在矩阵边缘越界。如果写四方向每一对关系会被检查两次结果虽然一样但代码里要处理四个越界分支出错概率更高。判断条件长这样if (j 1 n) { int cur maze[i][j] - A; int nxt maze[i][j 1] - A; if (pipe[cur][3] pipe[nxt][2]) // 当前向右开口右侧向左开口 merge(i * n j, i * n j 1); }3. 并查集合并与主循环3.1 二维坐标转一维编号并查集操作的是“数组索引”不是“二维坐标”。所以第一步是把每个格子的坐标映射成一个唯一的整数。假设矩阵是m行n列那么第i行第j列的格子编号是int id i * n j;这个公式很多人写的时候会迷惑最容易犯的错误是写成i * m j。i * n j的意思很直白每行有n个格子现在在第i行前面已经有i行完整的格子也就是i*n个再加上当前行第j个就是全局编号。比如一个3行4列的矩阵(2, 1)这个位置前面有2行共8个格子加上第1列编号就是9也就是数组下标9。这么编号之后并查集数组只需要开m * n个空间这道题最大50×50开2505个足够了。3.2 完整可运行代码C把方向数组、编号公式和并查集合并起来就能得到一个非常紧凑的解法#include bits/stdc.h using namespace std; const int pipe[11][4] { {1, 0, 1, 0}, {1, 0, 0, 1}, {0, 1, 1, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 0, 1, 1}, {1, 0, 1, 1}, {0, 1, 1, 1}, {1, 1, 1, 0}, {1, 1, 0, 1}, {1, 1, 1, 1} }; vectorstring maze; int fa[2505]; int find(int x) { if (fa[x] ! x) fa[x] find(fa[x]); return fa[x]; } bool mergeSets(int a, int b) { int ra find(a); int rb find(b); if (ra rb) return false; fa[ra] rb; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; while (cin m n, !(m -1 n -1)) { maze.resize(m); for (int i 0; i m; i) cin maze[i]; int total m * n; for (int i 0; i total; i) fa[i] i; int ans total; for (int i 0; i m; i) { for (int j 0; j n; j) { int curIndex i * n j; int curType maze[i][j] - A; // 检查右边的格子 if (j 1 n) { int rightType maze[i][j 1] - A; if (pipe[curType][3] pipe[rightType][2]) { if (mergeSets(curIndex, i * n j 1)) ans--; } } // 检查下方的格子 if (i 1 m) { int downType maze[i 1][j] - A; if (pipe[curType][1] pipe[downType][0]) { if (mergeSets(curIndex, (i 1) * n j)) ans--; } } } } cout ans \n; } return 0; }这段代码里我用了一个小优化初始化ans total每次合并成功就减1最后直接输出ans。这比最后遍历一遍所有节点再数根更好理解也省一次循环。如果习惯了数根的方式等价的写法是int ans 0; for (int i 0; i total; i) { if (find(i) i) ans; }两种写法都对ans--的方式要求mergeSets返回是否真的发生了合并否则两个已经在同一个集合里的节点也会被误减。3.3 路径压缩和按秩合并要不要写find函数里加一句fa[x] find(fa[x])就是路径压缩这道题必须写。虽然最大只有2500个节点不压缩也能过但压缩之后几乎可以让并查集操作复杂度接近常数。至于按秩合并我一般不在这种小数据量题目里专门维护rank数组因为路径压缩已经能让复杂度非常可观了。如果你是想练手把并查集写完整或者经常要处理10万级以上节点的大图那还是建议按秩合并也写上。4. 实测中的高频失分点与自测样例4.1 输入顺序和结束条件题目里先读m再读n也就是“行数 列数”不是“列数 行数”。有些题是n m很容易惯性写成反的。我见过一个同学第一次提交就是死在这个地方矩阵宽高搞反导致编号公式也错了。结束条件是两个数都是-1。安全写法是while (cin m n, !(m -1 n -1))这样只要输入存在就尝试读然后判断是否继续。不要写成while (scanf(%d%d, m, n) m ! -1 n ! -1)这种这种在m-1、n0这种边界上会有隐患虽然题目里不会出现但习惯要养好。4.2 自己动手构造自测用例下面这几个用例非常小适合拿来验证代码逻辑。建议拿到模板之后先把它们跑通再提交。输入期望输出说明1 1 K1只有一块地必然一套灌溉区域1 2 F F1两个水平管左右对接能连通1 2 A B2A向右无开口B向左无开口连不上2 1 E E1两根竖直管上下对接能连通2 2 K K / K K1四个四通管全连通2 2 K B / F D4每个格子的开口都接不上邻居最后一个用例可以手动验证一下K向下、右均有开口但右边的B没有向左的开口下面的F没有向上的开口所以K和谁都连不上同样B向下的开口为0接不到DF向右的开口为1但D向左的开口为0也接不上。最终4个格子各自成块。4.3 统计根之前要不要先find一遍如果你用“数fa[i] i”这种方式统计答案有一个细节值得注意如果某个非根节点的父指针还指向一个非根节点fa[i] i自然为假如果路径压缩还没完全压完有一些节点的父指针指向的可能是根也可能是别的节点。为了稳妥统计时最好直接写find(i) i这样会强制把所有节点压缩一遍保证结果一定是正确的。用mergeSets返回值来ans--的方式就没有这个烦恼因为它只在真正发生合并的时候减一。我实际写题的时候更偏好这种方式省心。4.4 方向表本身是最容易写错的地方方向表一旦写错整个程序就没有意义了。调试方法是把每个字符对应的四个方向打印出来对着原题图形核对一遍。可以写一个非常简单的打印函数void debugPrint(char ch) { int t ch - A; cout ch : up pipe[t][0] down pipe[t][1] left pipe[t][2] right pipe[t][3] endl; }把A到K都打一遍核对A是“上左”、B是“上右”这些基本特征。我印象最深的是第一次写这题时把C和D的方向搞反了样例那种稍微复杂一点的矩阵就错换单点测试又完全正常最后就是靠这种打印才定位到问题。5. 从HDU1198到更多网格连通问题5.1 另一种解法Flood Fill并查集不是唯一的解法。DFS或BFS同样能解决这个问题遍历矩阵遇到没访问过的格子就开启一次搜索把当前格子能连通的邻居全部标记访问每启动一次DFS就代表找到了一个新的连通块。不过直接用DFS/BFS有一个麻烦题目的“模拟部分”还是要做而且DFS代码里的方向判断通常写在递归函数里逻辑并不会比并查集简单。两套写法的复杂度都在O(m*n)常数也差不多区别在于思维模型不同。DFS/BFS更像是“慢慢浸水”并查集更像是“搭积木然后数堆数”。5.2 并查集写法的优势场景如果题目只问最终连通块数量DFS/BFS和并查集其实都能用。但有些场景只有并查集好用动态加边图不是一次性给你的而是边加边问“当前有多少个连通块”。这种在线查询用并查集可以在每次加边后O(1)维护答案。合并后还要查两个特定节点的关系并查集天生支持“查询两个元素是否同属于一个集合”。数据规模非常大递归DFS容易爆栈BFS又要维护队列并查集只要一个数组反复找根。HDU1198就是典型的“所有边一开始就知道”的静态图用并查集反而有点“杀鸡用牛刀”但如果把它当作练手题你能一次性把“建模方向数组”和“并查集模板”两个技能都练到。5.3 这类题的通用建模思路从HDU1198可以总结出一个很通用的建模套路凡是遇到“格子有方向、相邻格子有条件才能连接”的题先不要急着写搜索先想清楚每个格子需要保存什么信息。常见的信息类型有三种格子本身是否可通行比如迷宫题通常用0/1矩阵表达格子之间的连接依赖方向比如本道的开口对接可以用长度4的布尔数组格子有额外属性比如权值、颜色对应到并查集里就是带权并查集或扩展域把棋盘看成图、把格子编号节点、把规则转成邻接条件这套思路比背模板更重要。HDU1198看上去只是个小水题但它的价值就是把“网格图建模”这个通用技能训练了一遍。理解了这道题之后再看“水管工”“电路连通”“宝箱锁”之类的题你会发现基本都是换了个皮肤而已。最后说一个我在实际做题中的体会像HDU1198这种题最忌讳一上来就写代码。我后来每次做需要“规则判断集合合并”的题都会先在纸上把方向表、合并条件和编号公式写清楚再开始敲代码。因为并查集本来就没什么技术含量真正出bug的永远是“方向表写错”“编号公式用错”“边界条件漏判”这三类问题。你可以把这篇文章里的自测用例存下来以后遇到类似建模题先跑一遍这些用例保底再往上扩展。