题目分析本题设定在2126 21262126年彗星Swift‑Tuttle \texttt{Swift‑Tuttle}Swift‑Tuttle撞击地球后网络中的部分链接被切断同时一些AI \texttt{AI}AI程序发生了变异。两个程序Paskill \texttt{Paskill}Paskill和Lisper \texttt{Lisper}Lisper在网络中移动并遵循以下规则每个节点被首次访问时会被标记。Paskill \texttt{Paskill}Paskill标记为PASKILL_VISITED \texttt{PASKILL\_VISITED}PASKILL_VISITEDLisper \texttt{Lisper}Lisper标记为LISPER_VISITED \texttt{LISPER\_VISITED}LISPER_VISITED。Paskill \texttt{Paskill}Paskill进入节点后会激活一个修改过的Prolog \texttt{Prolog}Prolog解释器该解释器会反向编译并销毁任何后续进入的程序。因此Paskill \texttt{Paskill}Paskill永远不会重复进入已访问过的节点。Lisper \texttt{Lisper}Lisper进入节点后会激活一个变异为无限循环的Hello World \texttt{Hello World}Hello World程序使得任何其他程序包括Lisper \texttt{Lisper}Lisper自身都无法再次进入该节点。因此Lisper \texttt{Lisper}Lisper也不会重复进入已访问过的节点。如果Lisper \texttt{Lisper}Lisper试图进入一个已被Paskill \texttt{Paskill}Paskill访问过的节点Lisper \texttt{Lisper}Lisper会被销毁。如果两个程序同时到达同一节点它们会相互湮灭。如果两个程序都无法移动它们都会停止被困。两个程序移动速度相同。移动规则Paskill \texttt{Paskill}Paskill从当前节点出发字母顺序向前搜索相邻且未访问的节点循环绕回Lisper \texttt{Lisper}Lisper字母顺序向后搜索相邻节点循环绕回但Lisper \texttt{Lisper}Lisper允许进入已被Paskill \texttt{Paskill}Paskill访问过的节点这会导致自己被销毁。输出要求按照Paskill \texttt{Paskill}Paskill优先的顺序输出终止事件及发生节点。解题思路1. 图的存储节点标签为单个大写字母A AA到Z ZZ共最多26 2626个节点。使用邻接表存储无向图。输入格式为A:BD;C:BD;F:E;G:DEH;H:EG.AH每个节点描述为节点:邻居列表多个描述用;分隔以.结束。之后紧跟两个起始节点先Paskill \texttt{Paskill}Paskill的起点再Lisper \texttt{Lisper}Lisper的起点。2. 构造图解析每行输入提取每个节点的邻居。由于每条链接至少会被提及一次但可能重复需要在构建后对每个节点的邻居列表排序并去重。3. 模拟移动模拟的核心是交替移动由于速度相同每次两个程序各自移动一步先检查当前是否在同一节点模拟开始前及每次移动后若是则“相互湮灭”。标记当前两个节点为对应的访问状态。分别为Paskill \texttt{Paskill}Paskill和Lisper \texttt{Lisper}Lisper计算下一步节点Paskill \texttt{Paskill}Paskill从当前节点的邻居列表中先找字母顺序大于当前节点且未访问的若找不到再循环从头找第一个未访问的。Lisper \texttt{Lisper}Lisper从当前节点的邻居列表中先找字母顺序小于当前节点且未访问或已被Paskill \texttt{Paskill}Paskill访问的若找不到再循环从末尾找第一个未访问或已被Paskill \texttt{Paskill}Paskill访问的。根据下一步节点的情况判断终止事件若两者下一步相同 → 相互湮灭。若Lisper \texttt{Lisper}Lisper的下一个节点已被Paskill \texttt{Paskill}Paskill访问过 →Lisper \texttt{Lisper}Lisper被销毁。若Paskill \texttt{Paskill}Paskill无法移动 →Paskill \texttt{Paskill}Paskill被困此时还需检查Lisper \texttt{Lisper}Lisper的状态。若Lisper \texttt{Lisper}Lisper无法移动 →Lisper \texttt{Lisper}Lisper被困。否则更新当前位置继续下一轮移动。4. 事件优先级根据题目要求如果多个事件同时发生先提及Paskill \texttt{Paskill}Paskill。代码中通过条件判断的顺序来体现优先级。代码实现// Network Wars// UVa ID: 173// Verdict: Accepted// Submission Date: 2016-02-21// UVa Run Time: 0.029s//// 版权所有 (C) 2016, 邱秋. metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorvectorintnodes;// 邻接表共 26 个节点boolinitializedfalse;// 是否已初始化邻接表intpaskill,lisper;// 当前所在节点intvisited[26];// 节点访问状态constintUNVISITED0;// 未访问constintPASKILL_VISITED1;// Paskill 访问过constintLISPER_VISITED2;// Lisper 访问过constintNONE-1;// 无法移动// 根据输入行构建图并提取起始节点voidbuildGraph(string line){// 首次调用时初始化邻接表if(initializedfalse){for(inti0;i26;i){vectorintconnected;nodes.push_back(connected);}initializedtrue;}else{// 后续调用时清空之前的图数据for(inti0;inodes.size();i)nodes[i].clear();}intindex0;// 解析节点描述部分直到遇到 .while(true){string block;// 提取一个完整节点描述如 A:BDwhile(line[index]!;line[index]!.){if(isalpha(line[index])||line[index]:)blockline[index];index;}// 处理无向边节点 block[0] 与 block[2..] 之间互连for(inti2;iblock.length();i){nodes[block[0]-A].push_back(block[i]-A);nodes[block[i]-A].push_back(block[0]-A);}if(line[index].)break;// 描述部分结束index;// 跳过 ;}// 跳过 寻找起始节点index;while(isalpha(line[index])false)index;paskillline[index]-A;// Paskill 起点while(isalpha(line[index])false)index;lisperline[index]-A;// Lisper 起点// 对每个节点的邻居排序并去重for(inti0;inodes.size();i){sort(nodes[i].begin(),nodes[i].end());intnunique(nodes[i].begin(),nodes[i].end())-nodes[i].begin();nodes[i].erase(nodes[i].begin()n,nodes[i].end());}}// 计算 Paskill 下一步移动到的节点字母顺序向前循环绕回intgetNodeForward(){// 先找比当前节点大的未访问邻居for(inti0;inodes[paskill].size();i)if(nodes[paskill][i]paskillvisited[nodes[paskill][i]]UNVISITED)returnnodes[paskill][i];// 若没有则从头找第一个未访问的邻居for(inti0;inodes[paskill].size();i)if(visited[nodes[paskill][i]]UNVISITED)returnnodes[paskill][i];returnNONE;// 无路可走}// 计算 Lisper 下一步移动到的节点字母顺序向后循环绕回// 注意Lisper 允许进入已被 Paskill 访问过的节点intgetNodeBackward(){// 先找比当前节点小的且未访问或已被 Paskill 访问的邻居for(intinodes[lisper].size()-1;i0;i--)if(nodes[lisper][i]lisper(visited[nodes[lisper][i]]UNVISITED||visited[nodes[lisper][i]]PASKILL_VISITED))returnnodes[lisper][i];// 若没有则从后往前找第一个未访问或已被 Paskill 访问的邻居for(intinodes[lisper].size()-1;i0;i--)if(visited[nodes[lisper][i]]UNVISITED||visited[nodes[lisper][i]]PASKILL_VISITED)returnnodes[lisper][i];returnNONE;// 无路可走}// 模拟两个程序的移动过程voidwalk(){fill(visited,visited26,UNVISITED);while(true){// 情况 1两者在同一节点相互湮灭if(paskilllisper){coutBoth annihilated in node (char)(Apaskill)\n;break;}// 标记当前节点visited[paskill]PASKILL_VISITED;visited[lisper]LISPER_VISITED;// 计算下一步intpaskillNextgetNodeForward();intlisperNextgetNodeBackward();// 情况 2两者都有下一步可行if(paskillNext!NONElisperNext!NONE){// 情况 2.1下一步进入同一节点 → 相互湮灭if(paskillNextlisperNext){coutBoth annihilated in node (char)(ApaskillNext)\n;break;}// 情况 2.2Lisper 的下一步已被 Paskill 访问过 → Lisper 被销毁if(visited[lisperNext]PASKILL_VISITED){coutLisper destroyed in node (char)(AlisperNext)\n;break;}// 正常移动paskillpaskillNext;lisperlisperNext;continue;}// 情况 3Paskill 无法移动if(paskillNextNONE){coutPaskill trapped in node (char)(Apaskill);// 同时 Lisper 也无法移动 → 两者都被困if(lisperNextNONE)cout Lisper trapped in node (char)(Alisper);// 或者 Paskill 被困时所在的节点正好是 Lisper 的下一步 → 相互湮灭elseif(paskilllisperNext)cout Both annihilated in node (char)(Apaskill);// 或者 Lisper 的下一步已被 Paskill 访问过 → Lisper 被销毁elseif(visited[lisperNext]PASKILL_VISITED)cout Lisper destroyed in node (char)(AlisperNext);cout\n;break;}// 情况 4Lisper 无法移动Paskill 有下一步if(lisperNextNONE){coutLisper trapped in node (char)(Alisper)\n;break;}}}intmain(){cin.tie(0);cout.sync_with_stdio(false);string line;while(getline(cin,line),line!#){buildGraph(line);walk();}return0;}总结本题模拟过程虽然规则较多但核心是理解两个程序的移动规则和不同终止条件的优先级。实现时注意无向图的邻接表构建。字母顺序的循环搜索。Lisper \texttt{Lisper}Lisper的特殊性允许进入Paskill \texttt{Paskill}Paskill访问过的节点这会导致自己销毁。事件判断的顺序必须符合题目要求先Paskill \texttt{Paskill}Paskill。