★ FEATURED ARTICLE 题目描述一个孩子绘制了NNNN≤100N \le 100N≤100个带编号的彩色圆圈。他用彩色有向线段连接了其中一些圆圈。任意一对圆圈之间可以存在多条不同颜色的线段。每种颜色无论是圆圈颜色还是线段颜色都被赋予一个不超过100100100的正整数。游戏开始时孩子首先选择三个互不相同的整数LLL、KKK、QQQ均在111到NNN之间。然后他在圆圈LLL中放置一个棋子在圆圈KKK中放置另一个棋子随后按照以下规则移动棋子只能沿线段方向移动若要将一个棋子沿某条线段移动则该线段的颜色必须与另一个棋子所在圆圈的颜色相同两个棋子不能同时位于同一个圆圈移动顺序自由可以连续移动同一个棋子当任意一个棋子到达圆圈QQQ时游戏立即结束。要求计算使游戏结束所需的最少移动次数如果无法结束则报告无解。输入格式第一行包含一个整数表示数据集的个数。该行后有一个空行。每个数据集的第一行包含四个整数N,L,K,QN, L, K, QN,L,K,Q。第二行包含NNN个整数c1,c2,…,cNc_1, c_2, \dots, c_Nc1,c2,…,cN表示圆圈111到NNN的颜色。第三行包含一个整数MMM0≤M≤100000 \le M \le 100000≤M≤10000表示线段总数。接下来MMM行每行描述一条有向线段包含三个整数Aj,Bj,CjA_j, B_j, C_jAj,Bj,Cj表示从AjA_jAj到BjB_jBj的线段颜色为CjC_jCj。数据集之间用一个空行分隔。输出格式对于每个测试用例第一行输出YES如果游戏可以结束或NO否则。若答案为YES第二行输出一个整数 —— 最少移动次数。相邻测试用例的输出之间打印一个空行。样例样例输入1 5 3 4 1 2 3 2 1 4 8 2 1 2 4 1 5 4 5 2 5 1 3 3 2 2 3 2 4 5 3 1 3 5 1样例输出YES 3题目分析本题是一个双棋子状态空间搜索问题。两个棋子的位置共同构成一个状态(x,y)(x, y)(x,y)其中xxx和yyy分别是两个棋子所在的圆圈编号且必须满足x≠yx \ne yxy。初始状态为(L,K)(L, K)(L,K)目标状态为任意一个棋子到达QQQ即xQx QxQ或yQy QyQ。每次移动选择一个棋子将其沿一条有向边移动到新位置移动的合法性取决于另一个棋子所在圆圈的颜色与该边颜色是否相同并且移动后两个棋子不能重合。因为每次移动的代价均为111所以问题转化为在状态图上求从初始状态到任意目标状态的最短路径长度。状态总数最多为N×(N−1)≤9900N \times (N-1) \le 9900N×(N−1)≤9900每个状态可转移的边数依赖于两个棋子的出边数量总边数M≤10000M \le 10000M≤10000因此使用广度优先搜索BFS\texttt{BFS}BFS可以在有限时间内得到答案。解题思路状态表示与转移设dist[x][y]\textit{dist}[x][y]dist[x][y]表示到达状态(x,y)(x, y)(x,y)所需的最少移动次数初始dist[L][K]0\textit{dist}[L][K] 0dist[L][K]0。使用队列进行BFS\texttt{BFS}BFS。对于当前状态(u,v)(u, v)(u,v)尝试移动第一个棋子位于uuu遍历所有从uuu出发的边(u→nxt)(u \to nxt)(u→nxt)颜色为colcolcol。若colcolcol等于另一个棋子所在圆圈vvv的颜色circleColor[v]\textit{circleColor}[v]circleColor[v]并且nxt≠vnxt \ne vnxtv则移动合法。如果nxtQnxt QnxtQ则游戏结束当前步数加111即为答案。否则若dist[nxt][v]\textit{dist}[nxt][v]dist[nxt][v]未访问则更新并入队。同理移动第二个棋子位于vvv时需要检查颜色是否等于circleColor[u]\textit{circleColor}[u]circleColor[u]且nxt≠unxt \ne unxtu并判断是否到达QQQ。算法流程读入数据集。存储圆圈颜色数组circleColor[1..N]\textit{circleColor}[1..N]circleColor[1..N]。建立邻接表adj[u]\textit{adj}[u]adj[u]存储从uuu出发的所有边目标顶点颜色。初始化dist\textit{dist}dist为−1-1−1队列qqq。将(L,K)(L, K)(L,K)入队dist[L][K]0\textit{dist}[L][K] 0dist[L][K]0。不断出队按上述规则扩展状态直至队列为空或找到目标。若找到目标返回步数否则返回−1-1−1。根据返回值输出YES/NO及步数注意数据集间空行。复杂度分析状态数为O(N2)O(N^2)O(N2)每个状态扩展时需遍历两个棋子各自的出边总边数为MMM。最坏情况下每个状态遍历所有边总复杂度为O(N2⋅M)O(N^2 \cdot M)O(N2⋅M)。由于N≤100N \le 100N≤100M≤10000M \le 10000M≤10000最坏约为10810^8108次操作在时间限制内可行实际测试通过。空间复杂度O(N2)O(N^2)O(N2)用于存储距离数组。正确性说明BFS\texttt{BFS}BFS按层次扩展状态第一次到达目标状态时所经过的边数即为最短路径长度。由于移动代价均为111且转移条件仅依赖于当前状态满足最优子结构因此BFS\texttt{BFS}BFS给出的结果必然是最优解。代码实现// Game// UVa ID: 767// Verdict: Accepted// Submission Date: 2026-07-04// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintINF-1;// BFS 返回最小步数若不可达返回 -1intbfs(intN,intL,intK,intQ,constvectorintcircleColor,constvectorvectorpairint,intadj){vectorvectorintdist(N1,vectorint(N1,-1));queuepairint,intq;dist[L][K]0;q.push({L,K});while(!q.empty()){autocurq.front();q.pop();intucur.first,vcur.second;intddist[u][v];// 移动第一个棋子 ufor(autoe:adj[u]){intnxte.first,cole.second;if(colcircleColor[v]nxt!v){if(nxtQ)returnd1;if(dist[nxt][v]-1){dist[nxt][v]d1;q.push({nxt,v});}}}// 移动第二个棋子 vfor(autoe:adj[v]){intnxte.first,cole.second;if(colcircleColor[u]nxt!u){if(nxtQ)returnd1;if(dist[u][nxt]-1){dist[u][nxt]d1;q.push({u,nxt});}}}}return-1;}intmain(){intnumDatasets;cinnumDatasets;boolfirstCasetrue;for(intcaseIdx0;caseIdxnumDatasets;caseIdx){intN,L,K,Q;cinNLKQ;vectorintcircleColor(N1);for(inti1;iN;i)cincircleColor[i];intM;cinM;vectorvectorpairint,intadj(N1);for(inti0;iM;i){intA,B,C;cinABC;adj[A].push_back({B,C});}intansbfs(N,L,K,Q,circleColor,adj);// 输出数据集间空行if(!firstCase)cout\n;firstCasefalse;if(ans-1){coutNO\n;}else{coutYES\nans\n;}}return0;}总结本题的关键在于正确建模双棋子状态利用BFS\texttt{BFS}BFS求最短路径。由于状态数有限直接枚举所有状态并进行转移是可行的。需要注意的细节包括两个棋子不能同时位于同一圆圈转移时必须检查目标位置是否被另一棋子占据。颜色比较时使用另一个棋子所在圆圈的颜色而非当前移动棋子的颜色。初始三个整数L,K,QL, K, QL,K,Q互不相同但题目已保证不必额外校验。该解法思路清晰代码简洁能够通过所有测试数据。若NNN或MMM更大可能需要考虑更高效的状态压缩或双向BFS\texttt{BFS}BFS但在本题限制下标准BFS\texttt{BFS}BFS已足够。
阅读完成 · 觉得有帮助？
