UVa 255 Correct Move

题目分析这是一道关于国际象棋棋盘上王和后移动规则的模拟问题。题目描述了一个8×88 \times 88×8的棋盘格子编号从000到636363编号方式为逐行排列第000行0∼70 \sim 70∼7第111行8∼158 \sim 158∼15依此类推。棋盘上有两个棋子一个王King\texttt{King}King和一个后Queen\texttt{Queen}Queen。状态定义为王的位置和后的位置组成的二元组(king,queen)(king, queen)(king,queen)。当两个棋子不在同一格时状态是合法的。移动规则王的移动可以上下左右移动恰好111格但不能移动到后所在的位置。后的移动可以上下左右移动任意多格至少111格但不能越过王的位置即路径上不能有王。额外限制允许移动一个移动被称为允许的当且仅当移动本身是合法的移动的目标位置不是对方可以移动到的位置。换句话说王不能移动到后能走到的格子后也不能移动到王能走到的格子。问题要求对于每组输入包含三个整数kingkingking,queenqueenqueen,new_queennew\_queennew_queen需要依次判断给定的状态是否合法king≠queenking \neq queenkingqueen后的移动是否合法后能否从当前位置合法地移动到new_queennew\_queennew_queen后的移动是否允许移动目标是否不在王的可移动范围内如果以上都满足更新后的位置判断在新状态下王是否被锁死即王没有任何允许的移动。输出对应关系条件输出状态不合法kingqueenking queenkingqueenIllegal state\texttt{Illegal state}Illegal state状态合法但后的移动不合法Illegal move\texttt{Illegal move}Illegal move状态合法后的移动合法但不允许Move not allowed\texttt{Move not allowed}Move not allowed状态合法后的移动合法且允许且新状态下王有允许的移动Continue\texttt{Continue}Continue状态合法后的移动合法且允许但新状态下王无允许的移动Stop\texttt{Stop}Stop解题思路题目的核心在于正确实现三个判定函数isLegalMove\texttt{isLegalMove}isLegalMove判断后的移动是否合法。isAllowedMove\texttt{isAllowedMove}isAllowedMove判断后的移动是否允许即目标位置是否在王的一步可达位置内。isStop\texttt{isStop}isStop判断在新状态下王是否被锁死。棋盘坐标与编号转换棋盘编号从000到636363第rrr行第ccc列的编号为r×8cr \times 8 cr×8c。常用转换行号rowpos/8row pos / 8rowpos/8列号colpos%8col pos \% 8colpos%8同一行的格子范围[row×8,(row1)×8−1][row \times 8, (row1) \times 8 - 1][row×8,(row1)×8−1]同一列的格子pos,pos±8,pos±16,…pos, pos \pm 8, pos \pm 16, \dotspos,pos±8,pos±16,…1. 判断后的合法移动isLegalMove\texttt{isLegalMove}isLegalMove后的移动是直线的分为四个方向上、下、左、右。在每个方向上后可以移动任意多格但不能越过王的位置。实现方法向上列不变行递减从queen−8queen - 8queen−8开始每次减888直到遇到王或超出棋盘边界。向下列不变行递增从queen8queen 8queen8开始每次加888。向左行不变列递减从queen−1queen - 1queen−1开始每次减111但不能跨行即左边界为当前行的最左列。向右行不变列递增从queen1queen 1queen1开始每次加111但不能跨行即右边界为当前行的最右列。在这些方向上收集所有可以到达的格子不包括被王阻挡之后的格子然后检查movemovemove是否在集合中。注意由于王可能位于后的移动路径上需要提前终止该方向的搜索。2. 判断后的移动是否允许isAllowedMove\texttt{isAllowedMove}isAllowedMove后的移动允许当且仅当目标位置movemovemove不是王的一步可达位置。王的一步可达位置曼哈顿距离为111且在同一行或同一列上king−8king - 8king−8如果king−8≥0king - 8 \ge 0king−8≥0下king8king 8king8如果king864king 8 64king864左king−1king - 1king−1如果kingkingking不在最左列即king%8≠0king \% 8 \neq 0king%80右king1king 1king1如果kingkingking不在最右列即(king%8)≠7(king \% 8) \neq 7(king%8)7如果movemovemove等于上述任一位置则后的移动不允许否则允许。3. 判断王是否被锁死isStop\texttt{isStop}isStop在新的状态王位置不变后位置变为movemovemove下判断王是否有任何允许的移动。首先确定王的所有合法移动位置上下左右各一步且不能与后位置重合。然后需要排除后能走到的格子。注意这里“后能走到的格子”是指在新状态下后从新位置出发可以走到的所有格子包括新位置本身注意题目描述后不能移动到王的位置但王也不能移动到后能走到的位置。实际上后移动时不能“遇到”王但后占据的位置本身王是不能进入的。因此在判断王的允许移动时需要排除后的新位置本身因为两个棋子不能在同一格后从新位置出发沿四个方向直线可以到达的所有格子同样遇到王时停止因为王的阻挡会使后不能到达更远的格子实现方法收集后的“势力范围”向上、向下、向左、向右直线延伸遇到王则停止不包括王本身因为王在格子上后不能越过。然后检查王的四个可能移动位置如果任何一个位置不在后的势力范围内并且该位置在棋盘内且不是后本身则王有允许的移动返回false\texttt{false}false不是 Stop。否则返回true\texttt{true}true王被锁死是 Stop。代码实现// Correct Move// UVa ID: 255// Verdict: Accepted// Submission Date: 2016-05-12// UVa Run Time: 0.110s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 判断后的移动是否合法boolisLegalMove(intking,intqueen,intmove){setintnext;// 存储后可以合法移动到的所有位置// 向上移动列不变行递减for(intiqueen-8;i0;i-8){if(iking)// 遇到王不能越过停止break;next.insert(i);}// 向下移动列不变行递增for(intiqueen8;i64;i8){if(iking)// 遇到王停止break;next.insert(i);}// 向左移动行不变列递减不能跨行for(intiqueen-1;i(queen/8)*8;i--){if(iking)// 遇到王停止break;next.insert(i);}// 向右移动行不变列递增不能跨行for(intiqueen1;i(queen/81)*8;i){if(iking)// 遇到王停止break;next.insert(i);}// 检查目标位置是否在合法移动集合中returnnext.count(move)0;}// 判断后的移动是否允许即目标位置不能是王一步能到的位置boolisAllowedMove(intking,intmove){// 检查王的上方if((king-8)0(king-8)move)returnfalse;// 检查王的下方if((king8)64(king8)move)returnfalse;// 检查王的左方注意不能跨行if((king-1)(king/8*8)(king-1)move)returnfalse;// 检查王的右方if((king1)((king/81)*8)(king1)move)returnfalse;returntrue;}// 判断在新状态下王是否被锁死没有任何允许的移动boolisStop(intking,intqueen){setintdisallowed;// 存储后能走到的所有格子包括后本身// 向上收集后的势力范围for(intiqueen;i0;i-8)disallowed.insert(i);// 向下收集后的势力范围for(intiqueen;i64;i8)disallowed.insert(i);// 向左收集后的势力范围for(inti(queen/8)*8;i(queen/81)*8;i)disallowed.insert(i);// 检查王的上方是否可走if((king-8)0disallowed.count((king-8))0)returnfalse;// 检查王的下方是否可走if((king8)64disallowed.count((king8))0)returnfalse;// 检查王的左方是否可走if((king-1)(king/8*8)disallowed.count((king-1))0)returnfalse;// 检查王的右方是否可走if((king1)((king/81)*8)disallowed.count((king1))0)returnfalse;// 四个方向都不可走则王被锁死returntrue;}intmain(){cin.tie(0);cout.sync_with_stdio(false);intking,queen,move;while(cinkingqueenmove){// 1. 检查状态是否合法if(kingqueen){coutIllegal state\n;continue;}// 2. 检查后的移动是否合法if(isLegalMove(king,queen,move)false){coutIllegal move\n;continue;}// 3. 检查后的移动是否允许if(isAllowedMove(king,move)false){coutMove not allowed\n;continue;}// 4. 更新后的位置判断王是否被锁死queenmove;if(isStop(king,queen))coutStop\n;elsecoutContinue\n;}return0;}总结本题的关键在于准确理解三种判定逻辑合法移动后的直线路径不被王阻挡。允许移动后的目标位置不与王的可移动位置冲突。锁死判定在新状态下王的所有可能移动位置都在后的攻击范围内。代码实现时注意边界条件棋盘边缘、行边界以及王作为障碍物对后移动的影响。使用set\texttt{set}set来存储后的可达位置可以简化判断逻辑。