-1
我有一個網格，可以表示爲boolean[][]，例如，有效的蜂窩自動化遊戲中的以前的位置（像康威）
new boolean[][] {
{true, false, true, ...},
{false, true, false, ...}
{true, false, true, ...}
...
}
將是像一個網格：
O X O ...
X O X ...
O X O ...
...
其中O是/活着/真實，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上，左下角前一個刻度單元的組合很大程度上不受右上角刻度單元組合的影響。
當然，有一種方法可以找到有效的先前網格的總數，考慮到大多數單元不會相互影響的事實？
我主要是在尋找理解方法，而不是任何完整解決方案的代碼 - 如果您願意，請繼續前進！