题目描述Domino\texttt{Domino}Domino游戏采用282828张多米诺骨牌每张牌的两面分别标有数字000到666。两面数字相同的牌称为双块。游戏由两名玩家Red\texttt{Red}Red和Green\texttt{Green}Green进行双方各获得nnn张牌且牌堆不重复。游戏开始时拥有最大数字双块的玩家先手将该双块放置在桌面中央形成一条链链的两端称为“极端”。此后双方轮流行动每次行动时当前玩家必须从自己剩余的牌中选出一张将其放置在链的某一端使得该牌与极端相邻的那一面的数字与极端数字相同。放置后牌的另一面成为新的极端。若当前玩家没有任何牌能与任一极端匹配则必须跳过该回合。胜利条件率先将自己手中所有牌全部放完的玩家获胜。给定双方的初始牌组需要判断只有Red\texttt{Red}Red可能获胜只有Green\texttt{Green}Green可能获胜双方均可能获胜双方均不可能获胜。本题并非寻找必胜策略而是判断每位玩家是否存在至少一条合法的出牌路径使其最终获胜。输入格式输入包含多个测试用例每个测试用例占一行格式为n r11 r12 r21 r22 ... rn1 rn2 g11 g12 ... gn1 gn2其中nnn1≤n≤141 \le n \le 141≤n≤14表示Red\texttt{Red}Red和Green\texttt{Green}Green各自获得的牌数ri1 ri2r_{i1} \, r_{i2}ri1​ri2​表示Red\texttt{Red}Red的第iii张牌的两个数字gi1 gi2g_{i1} \, g_{i2}gi1​gi2​表示Green\texttt{Green}Green的第iii张牌的两个数字所有牌均不重复至少有一名玩家拥有一张双块每个数字均为000到666的整数。数字之间可由任意数量的空白字符分隔。相邻测试用例之间无空行。输入以一行n0n 0n0结束。输出格式对于每个测试用例输出一行内容为以下四种消息之一Only player Red can winOnly player Green can winBoth players can winNo players can win两个连续测试用例的输出之间用一个空行隔开。样例输入1 6 6 0 0 2 5 5 3 4 1 5 3 5 2 1 1 2 2 3 3 4 4 1 4 5 4 4 0输出Only player Red can win Both players can win No players can win Only player Green can win题目分析游戏的状态由以下要素决定当前链的两个极端数字左端和右端当前轮到哪名玩家行动Red\texttt{Red}Red和Green\texttt{Green}Green各自剩余的牌用位掩码表示共282828张牌。由于n≤14n \le 14n≤14双方总牌数为2n≤282n \le 282n≤28恰好等于全部牌的数量因此每个玩家的剩余牌集合可以表示为一个282828位的二进制掩码。游戏过程是一个确定性的状态转移过程每个状态下当前玩家从自己的剩余牌中枚举所有能与左端或右端匹配的牌放置后产生新状态若没有可用的牌则跳过回合。游戏终止于某玩家手中的牌数为000。我们需要判断的是从初始状态出发是否存在一条状态转移路径使得Red\texttt{Red}Red最终出完所有牌以及是否存在一条路径使得Green\texttt{Green}Green最终出完所有牌。这两者可以独立判断。由于状态空间有限虽然2282^{28}228理论上很大但实际可达状态数受牌数和链形态限制在n≤14n \le 14n≤14时完全可枚举可以使用广度优先搜索BFS\texttt{BFS}BFS遍历所有可达状态分别检查是否能够到达红方或绿方获胜的终止状态。解题思路状态表示将282828张牌分别编号为000到272727并建立数字对到编号的映射。每张牌记录其两个数字无序。定义结构体State\textit{State}State包含left、right当前链两端的数字turn当前行动玩家000表示Red\texttt{Red}Red111表示Green\texttt{Green}GreenmaskR、maskG各自剩余牌的位掩码282828位某位为111表示该牌仍在手中。初始状态首先从双方的牌中找出数字最大的双块。由于题目保证至少有一名玩家拥有双块因此可以唯一确定拥有该双块的玩家若最大双块数字相同则只可能有一张因为牌不重复。该玩家作为先手必须首先放置此双块。放置后链的两端数字均为该双块上的数字且该牌从先手玩家的掩码中移除。当前行动玩家切换为对方。广度优先搜索BFS\texttt{BFS}BFS分别对Red\texttt{Red}Red和Green\texttt{Green}Green作为目标玩家执行一次BFS\texttt{BFS}BFS判断是否存在获胜路径。BFS\texttt{BFS}BFS从初始状态开始用队列扩展所有可达状态。使用哈希集合记录已访问状态避免重复扩展。对于每个出队状态若maskR 0则Red\texttt{Red}Red已出完所有牌此时若目标为Red\texttt{Red}Red则返回true否则继续但若目标为Green\texttt{Green}Green则此状态不是Green\texttt{Green}Green的获胜状态因为Red\texttt{Red}Red先获胜了。若maskG 0同理判断目标是否为Green\texttt{Green}Green。否则根据turn确定当前玩家枚举其手中所有牌遍历282828位掩码。对于每张牌尝试将其放置在左端或右端若匹配生成新状态新链两端数字相应更新该牌从当前玩家的掩码中移除行动玩家切换为对方。若新状态尚未访问则入队。若当前玩家没有任何一张牌能与任一极端匹配则只能跳过回合生成一个turn取反、其余不变的状态若未访问则入队。BFS\texttt{BFS}BFS结束后仍未到达目标玩家的获胜状态则返回false。状态数估计虽然掩码有282828位但实际可达状态远小于2282^{28}228因为双方总牌数固定为2n2n2n链两端的数字受已放置的牌限制状态转移有向且无环牌数持续减少跳过回合不减少牌数但会切换玩家可能形成循环需用哈希去重。对于n≤14n \le 14n≤14实际状态数在可接受范围内BFS\texttt{BFS}BFS能够快速完成。复杂度分析每个状态转移枚举当前玩家的剩余牌最多282828张每张尝试左右两个方向常数小。状态数SSS不超过所有可能的掩码组合与链端组合最坏情况下在n14n14n14时约为O(228)O(2^{28})O(228)但实际远小于此完全可行。总时间复杂度O(S⋅28)O(S \cdot 28)O(S⋅28)空间复杂度O(S)O(S)O(S)。代码实现// Domino Game// UVa ID: 742// Verdict: Accepted// Submission Date: 2026-07-05// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 28张多米诺牌每张牌两个数字编号0~27intdomino[28][2];intidxMap[7][7];// 游戏状态structState{intleft,right;// 当前链两端数字intturn;// 0: Red, 1: Greenuint32_tmaskR,maskG;// 各自剩余牌的位掩码28位booloperator(constStateother)const{returnleftother.leftrightother.rightturnother.turnmaskRother.maskRmaskGother.maskG;}};// 哈希函数用于unordered_setstructStateHash{size_toperator()(constStates)const{uint64_th1(uint64_t)s.left60|(uint64_t)s.right54|(uint64_t)s.turn53|(uint64_t)s.maskR25|(uint64_t)s.maskG;return(size_t)h1;}};// 判断目标玩家target 0 表示 Red1 表示 Green是否有获胜路径boolcanWin(inttarget,constStateinit){queueStateq;unordered_setState,StateHashvisited;q.push(init);visited.insert(init);while(!q.empty()){State curq.front();q.pop();// 检查是否有人获胜if(cur.maskR0)returntarget0;// Red 出完if(cur.maskG0)returntarget1;// Green 出完uint32_tmask(cur.turn0)?cur.maskR:cur.maskG;boolhasMovefalse;// 枚举当前玩家的每张牌for(intid0;id28;id){if(!(mask(1uid)))continue;intadomino[id][0],bdomino[id][1];// 尝试匹配左端if(acur.left||bcur.left){hasMovetrue;intnewLeft(acur.left)?b:a;intnewRightcur.right;uint32_tnewMaskRcur.maskR,newMaskGcur.maskG;if(cur.turn0)newMaskR~(1uid);elsenewMaskG~(1uid);State nxt{newLeft,newRight,1-cur.turn,newMaskR,newMaskG};if(!visited.count(nxt)){if(nxt.maskR0target0)returntrue;if(nxt.maskG0target1)returntrue;visited.insert(nxt);q.push(nxt);}}// 尝试匹配右端if(acur.right||bcur.right){hasMovetrue;intnewRight(acur.right)?b:a;intnewLeftcur.left;uint32_tnewMaskRcur.maskR,newMaskGcur.maskG;if(cur.turn0)newMaskR~(1uid);elsenewMaskG~(1uid);State nxt{newLeft,newRight,1-cur.turn,newMaskR,newMaskG};if(!visited.count(nxt)){if(nxt.maskR0target0)returntrue;if(nxt.maskG0target1)returntrue;visited.insert(nxt);q.push(nxt);}}}// 当前玩家无牌可出跳过回合if(!hasMove){State nxt{cur.left,cur.right,1-cur.turn,cur.maskR,cur.maskG};if(!visited.count(nxt)){if(nxt.maskR0target0)returntrue;if(nxt.maskG0target1)returntrue;visited.insert(nxt);q.push(nxt);}}}returnfalse;}intmain(){// 初始化所有牌编号0~27intcnt0;for(inta0;a6;a)for(intba;b6;b){domino[cnt][0]a;domino[cnt][1]b;idxMap[a][b]cnt;cnt;}boolneedBlankfalse;intn;while(cinnn!0){uint32_tmaskR0,maskG0;// 读取 Red 的 n 张牌for(inti0;in;i){intx,y;cinxy;if(xy)swap(x,y);intididxMap[x][y];maskR|(1uid);}// 读取 Green 的 n 张牌for(inti0;in;i){intx,y;cinxy;if(xy)swap(x,y);intididxMap[x][y];maskG|(1uid);}// 找出最大双块的持有者intmaxDoubleVal-1,maxDoublePlayer-1,maxDoubleId-1;for(intid0;id28;id){if(domino[id][0]domino[id][1]){intvaldomino[id][0];if(maskR(1uid)||maskG(1uid)){if(valmaxDoubleVal){maxDoubleValval;maxDoublePlayer(maskR(1uid))?0:1;maxDoubleIdid;}}}}// 初始状态最大双块已由先手放下State init;init.leftinit.rightmaxDoubleVal;init.maskRmaskR;init.maskGmaskG;if(maxDoublePlayer0)init.maskR~(1umaxDoubleId);elseinit.maskG~(1umaxDoubleId);init.turn1-maxDoublePlayer;// 轮到对方boolredWincanWin(0,init);boolgreenWincanWin(1,init);if(needBlank)coutendl;needBlanktrue;if(redWingreenWin)coutBoth players can win\n;elseif(redWin!greenWin)coutOnly player Red can win\n;elseif(!redWingreenWin)coutOnly player Green can win\n;elsecoutNo players can win\n;}return0;}总结本题是一道典型的状态空间搜索问题关键点在于将游戏状态精确定义为链两端、当前玩家和双方剩余牌的掩码利用广度优先搜索BFS\texttt{BFS}BFS枚举所有可达状态分别判断两位玩家各自是否存在获胜路径使用哈希集合去重避免状态无限循环位掩码表示牌集合高效进行集合操作。该解法直接且可靠对于n≤14n \le 14n≤14的限制完全满足时间和空间要求。通过分别对两位玩家调用搜索函数可以清晰得到四种可能的结果。