algorithm - 人生博弈中合法的先前举动次数

考虑到康威生命游戏（或任何其他手机自动化游戏）中游戏的当前滴答声，如何才能找到在提供的滴答声中可以评估的合法先前滴答声的数量？
例如，假设生命游戏可以表示为：

0 0 0 0 0 ...
X 0 X 0 0 ...
0 X 0 0 0 ...
0 0 0 0 X ...
...

如果X是“alive/on/true”，而0是“dead/off/false”，或者更简单地说是一个boolean[][]，那么如何解决以下问题：

public static int numberOfValidPreviousTicks(boolean[][] current) {
    return -1; // return answer
}

很明显，我们可以从网格大小中找到所有可能的前一个游戏状态，并使用常规规则确定该状态是否会计算为当前状态。
但是，必须有一些明显的方法来加速这个过程，这样它才不会O(2^n)（其中n是网格中的单元格总数）。
缓存当然可以在某些地方有所帮助，但它到底能放在哪里呢？
任何帮助都将不胜感激

最佳答案

对于m*m板，您可以使用动态编程在O(m*8^m)中执行此操作。
其思想是从板的顶部开始向下计算，为第i-1, i位置的每一对行计算所有可以在第i+1位置的行，以给出正确的第i行输出。
这比2^O(n) = 2^(O(m*m))好，但速度很慢。
我不认为你会做得更好。

关于algorithm - 人生博弈中合法的先前举动次数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41858877/