核心内容摘要
5个核心步骤：Resistance Gene Identifier抗性基因检测从入门到精通
题目分析The Spot Game\texttt{The Spot Game}The Spot Game是一个基于N×NN \times NN×N棋盘的游戏双方轮流执行操作操作包括在空白格子中放置一个黑子用 “” 表示从棋盘上移除一个已有的黑子用 “-” 表示。
游戏规则如下如果当前棋盘状态或其旋转90°90°90°、180°180°180°后的状态在之前的游戏过程中已经出现过则当前玩家立即输掉游戏对方获胜游戏最多进行2N2N2N步如果在2N2N2N步后仍未出现重复状态则游戏平局。
输入包含多组游戏每组游戏的第一行为棋盘大小NNN2≤N≤502 \leq N \leq 502≤N≤50接下来是2N2N2N行操作每行包含坐标(x,y)(x, y)(x,y)和操作符或-。
输入以000结束。
输出应指出获胜的玩家和获胜的步数或声明游戏平局。
解题思路核心问题我们需要高效地检测棋盘状态是否重复包括旋转后的状态。
由于棋盘最大可达50×5050 \times 5050×50直接表示状态矩阵并比较的复杂度较高但我们可以将状态编码成字符串进行存储和比较。
状态编码我们可以用一个长度为N×NN \times NN×N的字符串表示棋盘状态用‘1’表示该位置有黑子用‘0’表示该位置为空。
每次操作后更新对应的字符。
旋转处理题目要求判断当前状态是否与之前任一状态在旋转0°0°0°、90°90°90°顺时针、90°90°90°逆时针或180°180°180°后相同。
因此我们需要编写函数分别生成当前状态的三种旋转状态。
为了便于比较我们始终将旋转后的状态也编码为字符串并存储到集合中。
查找重复使用哈希表如mapstring, int存储所有出现过的状态包括旋转后的状态值为首次出现时的步数。
每步操作后生成当前状态的四个等价状态原状态 三种旋转检查它们是否已经在哈希表中如果存在则当前玩家输对方获胜否则将这四个状态插入哈希表记录当前步数。
时间复杂度每一步需要生成四个字符串长度均为N2N^2N2最多2N2N2N步因此总时间复杂度约为O(N
O(N^
O(N
在N≤50N \leq 50N≤50时是可接受的。
代码实现说明以下代码使用C\texttt{C}C编写主要步骤包括读取NNN若为 0 则结束初始化状态字符串和哈希表循环处理2N2N2N步操作更新棋盘状态检查当前状态是否已出现生成旋转状态并插入哈希表根据是否出现重复状态输出结果。
参考代码// The Spot Game// UVa ID: 141// Verdict: Accepted// Submission Date:
// UVa Run Time:
003s//// 版权所有C2016邱秋。
metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;stringrotateCW90(string matrix,intn){string newMatrix;for(inti1;in;i)for(intj1;jn;j)newMatrixmatrix[(n-