c++ - 如何以尽可能低的时间复杂度检测网格中的循环？

Question

我有一个最多 35 个字符的网格，它可能是 (1x35..5x7) 或其他任何东西。网格上每个单元格的值只能是二进制的。在模拟具有某些动作的游戏时，这意味着在经过移动。如果我必须检测这个游戏的周期/周期，我可以在尽可能低的时间复杂度内使用什么算法/数据结构？我尝试了一种基于 log n 树的方法来存储网格的状态，但是当周期大于 2^17 时，它对于我的目的来说不够快。有没有一种技术可以在不占用太多内存的情况下对网格状态执行散列？

Answer 1

网格是一个 35 位数字，因此您可以将网格存储为整数（在 64 位机器上）或 2 个字在较小的数字上。你可以将你已经看到的状态保存在一个巨大的直接地址数组或哈希表中。