我有一个可以表示为boolean[][]的网格，例如
new boolean[][] {
{true, false, true, ...},
{false, true, false, ...}
{true, false, true, ...}
...
}
将表示类似于的网格
O X O ...
X O X ...
O X O ...
...
其中CCD_ 2是开/活/真并且X是关/死/假。
网格总是矩形或正方形的尺寸(长度或宽度)可以是非平凡的长度(大于20)
这种蜂窝自动化的规则是：
如果以下4个细胞中恰好有一个在当前刻度上活动，则一个细胞在下一个刻度上活动：
- 此单元格
- 下面的单元格
- 右边的单元格
- 右侧下方的单元格
在所有其他情况下，细胞在下一次滴答声中死亡。
一种特殊情况是网格最下面一行和最右边一列的单元格，它们在下一个刻度时都会被删除。
例如，的输入网格
O X X
X X O
X X X
将是
O O
X O
在下一个刻度上，
所以游戏规则很简单。
问题是，从任何给定的位置，如何确定将评估为当前刻度的有效先前刻度的总数？
很明显，如果输入是m x n网格，则可以生成网格大小为m+1 x n+1的每个可能的网格组合，评估刻度并比较位置。然而，这将是一个2^(O(m x n))的解决方案，并且在这种方法中有很多冗余。
我已经编码了一种方法，它计算出每一个可能的底部行组合，然后将这些组合成一个"加权底部行"，然后继续向上遍历网格。这消除了反复计算相同结果的重复，但显然仍然可以改进。类似的方法是从右侧向内移动，或者两者结合。
我的想法是，对于任何给定的单元格，它只受当前单元格左上角单元格的影响。例如，在10x10上，左下角上一个刻度上的单元格组合在很大程度上不受右上角上一刻度上单元格组合的影响。
当然有一种方法可以找到有效的先前网格的总数，该方法考虑到大多数单元格不会相互影响这一事实吗？
我主要是想了解这种方法，而不是任何完整解决方案的代码——如果你愿意，请继续！
如果我很理解你的问题，你想计算一些配置的预映像。一般来说，这个问题是NP完全的，所以在合理的时间内很难解决。不，你不必构建每一个配置并测试它是否为你提供了一个开始的配置，但可能有些回溯会帮助你(似乎你尝试了类似的东西)，或者动态编程方法。