如何判断每次走棋后是否有n个连续的相同颜色的棋子？

Question

假设我有一些 2 名玩家的棋盘游戏。每个玩家轮流将棋盘上的棋子放置在随机位置。如果玩家在一行中拥有

n

连续棋子（垂直或水平），则玩家获胜。请注意，董事会可以无限期延长。

我想实现这样的游戏，但我不知道如何有效地检查获胜条件。在每次移动之后，我们可以粗略地检查所有 4 个方向，看看我们是否满足获胜条件，但这是每次移动之后的

O(n)

搜索。

我正在考虑缓存结果，尽管我认为这在这种情况下没有帮助。

例如，假设我们已将结果缓存在

(i - 1, j)

处，并且下一个片段放置在

(i, j)

处。我们可以使用前者的结果来计算后者的结果，所以这最终是一个 O(1) 搜索，但问题是，我们必须更新所有邻居的缓存结果，直到

k 

平方，所以我们遇到了与之前相同的问题。

有更好的方法来解决这个问题吗？

Answer 1

我会使用两种不相交的集合数据结构——一种用于垂直集，一种用于水平集。

当棋子被添加到棋盘上时，您可以在每个数据结构中为其创建一个集合。然后，在垂直方向上，将其集合与任意（最多 2 个）垂直相邻的相同颜色集合合并。在水平邻接中，您可以对水平邻接执行相同的操作。

您需要跟踪每个根集中的元素总数，当其中一个大于

n

时，您就获胜了。您不妨使用按大小联合而不是按排名联合。

如果为每个棋子提供一个等于前面移动次数的整数 ID，那么您可以为每个棋子使用一个动态数组，非常有效地实现这些不相交的集合数据结构。请参阅此答案中的实现：如何正确实现不相交集数据结构以在 Python 中查找生成森林？

这实际上需要每次移动恒定的摊销时间。

如果您正在进行某种需要撤消移动的回溯搜索，那么您应该跳过路径压缩（您的检查将花费 O(log n) 时间），或者使用仅更改每个操作的指针数量恒定。我建议将路径中途的节点直接链接到根。这将恢复恒定摊销时间操作，并将每次移动的更新限制为每次移动仅 8 个整数（每个不相交集数据结构中为 4 个）。在撤消堆栈中跟踪这些更新将使您能够有效地撤消每个更新以进行回溯。

Answer 2

假设每个细胞存储：

• 状态：无人认领，玩家1，玩家2
• 对于每个维度（水平/垂直）：包含相关单元格的连续游程长度。对于无人认领的单元格，将其视为 0。

为了避免昂贵的更新，我们仅保证连续运行结束时单元格的运行长度正确性。例如。如果您是一次跑步的最左边的单元格，则可以保证向右跑步的长度的正确性。

当玩家认领一个单元格时，检查 4 个相邻的单元格。

• 如果没有一个被同一玩家认领，则将两个维度都设置为 1。
• 如果同一玩家声称其中一个或多个，请更新相关运行的端点以反映新的长度。

示例 1：X = 无人认领； 0 = 玩家 0，1 = 玩家 1。 假设沿着某个维度我们有...XXXX000X000000XXXX...

...然后，玩家 0 声称将 3 个 0 的运行与 6 个 0 的运行分开的单元格。检查邻居时，我们发现有一条向左延伸 3 、向右延伸 6 的游程。对于新单元格，我们的运行次数为 10。在 O(1) 中，我们将水平维度上的 2 个端点更新为 10。

每次声明一个单元格时，我们在 O(1) 时间内最多更新 4 个单元格。因为我们知道游程的长度，所以我们可以在 O(1) 中找到端点。