algorithm - 无限棋盘井字游戏的最佳数据结构

Question

假设我正在设计一款在无限棋盘上玩的井字游戏。成功将三个标记放在水平、垂直或对角线上的玩家获胜。 表示它的最佳数据结构是什么？只能想到哈希表来记录位置。对于每个新位置，检查其周围环境以评估获胜。

还有其他更好的主意吗？

Answer 1

虽然你有一个无限的棋盘，你仍然应该为你的游戏分配坐标。坐标可以是从 0 到一个非常大的数字。

现在，您有一个几乎无限大的坐标。为什么不是一个简单的坐标字典？ C++:

std::map<std::pair<long, long>, MySquare> m;

例如，您在(460,670)，您想查看(461,671)。只需检查 (461,671) 是否在 m 中，如果不在，则添加一个新条目。

这种非常简单的设计非常可靠，因为它仅在您确实需要时才分配内存。

不要让自己过于复杂。