我有一个可以表示为的网格boolean[][]，例如
new boolean[][] {
{true, false, true, ...},
{false, true, false, ...}
{true, false, true, ...}
...
}
将代表一个网格，如：
O X O ...
X O X ...
O X O ...
...
其中O是 on/alive/true 并且 X 是 off/dead/false。
网格始终是尺寸（长度或宽度）的矩形或正方形，可以是非平凡的长度（大于 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))并且这种方法存在很多冗余。
我编写了一种方法，计算每个可能的底行组合，然后将它们组合成“加权底行”，然后继续向上遍历网格。这消除了一遍又一遍地计算相同结果的重复，但显然仍然可以改进。类似的方法是从右侧向内移动或两者结合。
我的想法是，对于任何给定的单元格，它只受当前单元格左上角的单元格的影响。例如，在 a10x10上，左下角的前一个刻度上的单元格组合在很大程度上不受右上角的前一个刻度上的单元格组合的影响。
当然有一种方法可以找到有效的先前网格的总数，同时考虑到大多数单元格不会相互影响的事实？
我主要是在寻找对该方法的理解，而不是寻找完整解决方案的任何代码-如果您愿意，请继续！