题目描述Slitherlink\texttt{Slitherlink}Slitherlink是一种在网格上进行的逻辑谜题。给定一个(2R1)×(2C1)(2R1) \times (2C1)(2R1)×(2C1)的字符网格其中包含网格点、数字格以及候选的绘制线段。每个内部格子即行、列均为偶数的位置可能是空格或数字0∼30 \sim 30∼3。玩家的目标是在相邻网格点之间绘制线段使得对于每个标有数字kkk的格子其四条邻边中恰好有kkk条被绘制所有被绘制的线段形成一条单一的回路即一个简单环不自交且无分支。本题不要求求解而是给定一个“候选方案”即所有线段已经用-和|标记需要验证该方案是否合法。输入格式第一行一个整数TTT表示测试用例数量。每个测试用例由一行两个正整数RRR、CCC均≤50\le 50≤50开始随后是(2R1)(2R1)(2R1)行每行(2C1)(2C1)(2C1)个字符描述完整网格。字符含义如下若行rrr与列ccc均为奇数则为表示网格点若rrr与ccc均为偶数则为空格或0~3表示数字格内容若rrr为奇数、ccc为偶数则为空格或-表示水平绘制的线段若rrr为偶数、ccc为奇数则为空格或|表示垂直绘制的线段。输入保证格式良好每个测试用例前有一个空行。输出格式对于每个测试用例输出一行Valid或Invalid表示候选方案是否满足所有约束。样例输入节选5 3 3 - 1| |2 - - | 1 | -- 1 |3| - 2 3 - - |3| |3| |3| |3| - - 2 2 -- |3|3| |3|3| -- 2 2 - 2| | -- | |2 - 3 4 -- | |2 - - |3 0 3| - -- | | 1 - 输出Invalid Invalid Invalid Invalid Valid题目分析本题的验证任务包含两个独立的约束条件缺一不可。第一项是局部约束——每个数字格周围的边数必须精确匹配。第二项是全局拓扑约束——所有绘制的边必须恰好构成一个环。局部约束的检查数字格位于行、列均为偶数的位置若从111开始计数则为偶数若用 基于000的索引则为奇数。对于每个数字kkk只需查看其上、下、左、右四个方向的字符是否为线段标记上/下为-左/右为|累加计数后与kkk比较即可。这一步是直接的时间复杂度为O(RC)O(RC)O(RC)。全局拓扑约束所有线段构成一个环等价于以下两个条件度数条件每个网格点的度数连接的线段数必须为000或222。若存在度数为111或≥3\ge 3≥3的点则要么出现端点无法形成环要么出现交叉或分支环自交或不单一。连通性条件所有度数为222的顶点必须属于同一个连通分量即整个图恰好只有一个环。若存在多个连通分量则会有多个环或孤立线段。要验证这两个条件我们需要将网格中的线段转化为图结构。网格点总数最多为(R1)(C1)≤2601(R1)(C1) \le 2601(R1)(C1)≤2601线段数最多约为2RC≤50002RC \le 50002RC≤5000因此可以显式构建图并检查。图的构建每个网格点对应一个顶点编号例如按行优先编号为row * (C1) col。遍历所有可能水平边行号为偶数列号为奇数和垂直边行号为奇数列号为偶数若该位置的字符为-或|则连接对应的两个顶点并同时增加这两个顶点的度数。同时使用并查集记录连通性。验证流程遍历所有顶点检查度数是否等于000或222。找到第一个度数为222的顶点若不存在则说明没有边或边不成环直接判为无效。从该顶点出发检查所有度数为222的顶点是否都与它在同一个并查集集合中。如果全部满足则图是一个单一环否则无效。注意孤立点度数为000是允许的因为未使用的网格点不影响环的构造。解题思路数据结构选择并查集用于高效合并连通顶点并查询连通性复杂度接近常数。一维数组存储网格使用vectorstring存储全部2R12R12R1行方便按行读取和随机访问。具体步骤读取输入注意每个测试用例前有一空行需要用getline读取并忽略。由于行内可能包含空格如数字格为空或空格必须使用getline读取完整行而不能用cin 。校验数字约束遍历所有数字格行索引为奇数列索引为奇数若从000开始计数。对每个字符ch若不为空格则计算其四边上的线段标记。若计数不等于ch - 0则标记无效并跳出。构建图并统计度数初始化顶点总数V (R1)*(C1)度数数组deg全零并查集对象。遍历水平边行i从0到2R步长2列j从1到2C-1步长2。若grid[i][j] -则连接顶点(i/2, (j-1)/2)与(i/2, (j1)/2)并增加度数。遍历垂直边行i从1到2R-1步长2列j从0到2C步长2注意必须包含最右侧列2C2C2C否则会漏掉右边界的垂直线。若grid[i][j] |则连接顶点((i-1)/2, j/2)与((i1)/2, j/2)。验证环条件遍历所有顶点若度数不是000或222则无效。记录第一个度数为222的顶点若不存在则无效。取该顶点的并查集根再次遍历所有度数为222的顶点若其根与记录的根不同则无效。若全部通过则为有效。复杂度分析时间每个测试用例需要O(RC)O(RC)O(RC)时间进行数字检查O(RC)O(RC)O(RC)时间遍历边并合并并查集O(RC)O(RC)O(RC)时间验证度数及连通性总复杂度O(RC)O(RC)O(RC)。空间O(RC)O(RC)O(RC)存储网格O((RC)2)O((RC)^2)O((RC)2)存储图顶点和并查集。由于R,C≤50R, C \le 50R,C≤50该算法非常高效。代码实现// Slitherlink// UVa ID: 11745// Verdict: Accepted// Submission Date: 2026-06-25// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 并查集classDSU{public:vectorintparent,rankv;DSU(intn){parent.resize(n);rankv.assign(n,0);for(inti0;in;i)parent[i]i;}intfind(intx){if(parent[x]!x)parent[x]find(parent[x]);returnparent[x];}voidunite(intx,inty){intrxfind(x),ryfind(y);if(rxry)return;if(rankv[rx]rankv[ry])parent[rx]ry;elseif(rankv[rx]rankv[ry])parent[ry]rx;else{parent[ry]rx;rankv[rx];}}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intR,C;cinRC;string dummy;getline(cin,dummy);// 消耗 R C 后面的换行introws2*R1,cols2*C1;vectorstringgrid(rows);for(inti0;irows;i){getline(cin,grid[i]);// 去除可能的 Windows 换行符if(!grid[i].empty()grid[i].back()\r)grid[i].pop_back();}boolvalidtrue;// 1. 检查数字约束for(inti1;irows;i2){for(intj1;jcols;j2){charchgrid[i][j];if(ch )continue;intkch-0;intcnt0;if(i-10grid[i-1][j]-)cnt;if(i1rowsgrid[i1][j]-)cnt;if(j-10grid[i][j-1]|)cnt;if(j1colsgrid[i][j1]|)cnt;if(cnt!k){validfalse;break;}}if(!valid)break;}if(!valid){coutInvalid\n;continue;}intvertexRowsR1,vertexColsC1;inttotalVvertexRows*vertexCols;vectorintdeg(totalV,0);DSUdsu(totalV);// 2. 构建图并统计度数// 水平边行 i 为偶数0,2,...,2R列 j 为奇数1,3,...,2C-1for(inti0;i2*R;i2){for(intj1;j2*C-1;j2){if(grid[i][j]-){introwi/2;intcol1(j-1)/2;intcol2(j1)/2;intv1row*vertexColscol1;intv2row*vertexColscol2;deg[v1];deg[v2];dsu.unite(v1,v2);}}}// 垂直边行 i 为奇数1,3,...,2R-1列 j 为偶数0,2,...,2C// 注意必须包含列 2C最右边一列for(inti1;i2*R-1;i2){for(intj0;j2*C;j2){if(grid[i][j]|){intcolj/2;introw1(i-1)/2;introw2(i1)/2;intv1row1*vertexColscol;intv2row2*vertexColscol;deg[v1];deg[v2];dsu.unite(v1,v2);}}}// 3. 检查度数及连通性intfirstDeg2-1;for(intv0;vtotalV;v){if(deg[v]!0deg[v]!2){validfalse;break;}if(deg[v]2){if(firstDeg2-1)firstDeg2v;}}if(valid){if(firstDeg2-1){validfalse;// 没有环}else{introotdsu.find(firstDeg2);for(intv0;vtotalV;v){if(deg[v]2dsu.find(v)!root){validfalse;break;}}}}cout(valid?Valid:Invalid)\n;}return0;}总结本题的关键在于将图形验证拆分为局部数字校验和全局环检测。局部校验简单直接而全局检测则需要将线段转化为图并利用并查集高效判断连通性。需要注意的细节包括读取含空格的网格行必须用getline垂直边的遍历范围必须覆盖所有列包括最后一列否则会漏掉边界线段度数检查和连通性检查缺一不可前者保证没有端点或交叉后者保证单环。该解法充分利用了题目规模较小的特点R,C≤50R, C \le 50R,C≤50使暴力建图成为可行方案时间复杂度为线性级别。对于更大规模的网格此方法仍然有效因为建图复杂度始终为O(RC)O(RC)O(RC)。