P13329 [GCJ 2012 #3] Havannah

Havannah 由 Christian Freeling 和 MindSports 创作。MindSports 和 Christian Freeling 并未参与，也未给 Google Code Jam 背书。

Havannah 是一款由 Christian Freeling 创作的抽象策略棋类游戏。Havannah 在一个六边形棋盘上进行，棋盘每边有 $S$ 个六边形格子。每个六边形格子有两条水平边和四条斜边。每个六边形用一对整数标识。棋盘左下角的格子为 $(1, 1)$。与 $(x, y)$ 相邻、指向两点钟方向的格子是 $(x, y+1)$，指向十点钟方向的相邻格子是 $(x+1, y)$。下图是 $S=5$ 时的棋盘示例：  在 Havannah 游戏中，每个格子最多只能被一个棋子占据。棋子一旦落下，不会被移走或移动。游戏目标是用棋子构成以下三种连通结构之一。获胜结构包括： - **环（ring）**：形成一个包围了一个或多个空格的环。即，至少有一个内部格子是空的。更具体地说，存在一个空格，它被棋子包围，与棋盘的外边界隔开。注意，这条规则与官方 Havannah 游戏不同。 - **桥（bridge）**：连接棋盘上任意两个角的结构。 - **叉（fork）**：连接棋盘六条边中任意三条的结构。角不算作任何一条边的一部分。 下图展示了获胜结构的例子：  你的程序需要判断，单一玩家的一系列落子是否形成了获胜结构。如果形成，则输出结构名称及完成该结构的步数。如果某一步同时完成了多个环、连接了多于两个角，或连接了多于三条边，依然只算作“环”、“桥”或“叉”。但如果某一步同时完成了不同类型的结构，你需要输出所有结构的名称。我们只关心首次形成获胜结构的那一步：之后的落子全部忽略。如果全部落子后棋盘上没有任何获胜结构，则输出 none。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组第一行为两个整数 $S$ 和 $M$，分别表示棋盘每边六边形的数量和落子数。接下来 $M$ 行，每行一个用空格分隔的二元组 $(x, y)$，表示落子的位置。所有落子都在 $S$ 阶棋盘范围内，且无重复。本组测试数据的棋盘初始为空。

对于每个测试用例，输出一行 "Case #$n$: "，后接如下之一： * none * bridge in move $k$ * fork in move $k$ * ring in move $k$ * bridge-fork in move $k$ * bridge-ring in move $k$ * fork-ring in move $k$ * bridge-fork-ring in move $k$ 测试用例编号从 1 开始，落子编号也从 1 开始。

**限制条件** **测试集 1（8 分，结果可见）** - 时间限制：~~30~~ 3 秒 - $1 \leq T \leq 200$ - $2 \leq S \leq 50$ - $0 \leq M \leq 100$ **测试集 2（12 分，结果隐藏）** - 时间限制：~~60~~ 6 秒 - $1 \leq T \leq 20$ - $2 \leq S \leq 3000$ - $0 \leq M \leq 10000$ 翻译由 ChatGPT-4.1 完成。