グリッドはboolean[][]として表すことができます。セルオートメーションゲームにおける有効な以前の位置（コンウェイと同様）
Oが真/ /生きている上にあり、Xがオフ/偽/死んでいる
O X O ...
X O X ...
O X O ...
...
：
new boolean[][] {
{true, false, true, ...},
{false, true, false, ...}
{true, false, true, ...}
...
}
は次のようにグリッドを表します。
グリッドは、非自明な長さ（20を超える）であることができる常に寸法（長さ又は幅）の矩形又は正方形である
このセル・オートマトンのルールは、次のとおり
-
- このセル
- ：正確に一つの以下の4個のセルが現在の目盛りの上に生きている場合、セルは次の目盛りの上に生きていますセルの下と右の他のすべての条件に
に右
- から
- セルの下のセルは、セルは次の目盛りに死んでいます。
特別なケースは、グリッドの一番下の行と一番右の列にあるセルで、次のティックですべて削除されます。例えば
、次の目盛りに
O O
X O
だろう
O X X
X X O
X X X
の入力グリッド、
だからゲームのルールは非常に簡単です。
質問は、どのような位置からでも、現在のティックに評価された有効な前のダニの総数をどのように決定できますか？
入力がm x nグリッドであるかどうかは明らかですが、グリッドサイズm+1 x n+1のすべての可能なグリッドコンビネーションを生成し、ダニを評価し、位置を比較することができます。しかし、これは2^(O(m x n))の解決策であり、このアプローチには多くの冗長性があります。
私は可能なすべての最下行の組み合わせを計算し、これらを「加重最下行」に結合し、次にグリッドを上向きにトラバースする方法をコーディングしました。これにより、同じ結果を繰り返し計算する重複はなくなりますが、明らかに改善することができます。同様のアプローチは、右側から内側に、またはその2つの組み合わせから内側に移動することです。
私の考えは、任意の特定のセルでは、現在のセルの斜め上にあるセルの影響を受けるだけです。例えば。10x10では、左下の前のダニのセルの組み合わせは、右上の前のダニのセルの組み合わせによってほとんど影響を受けません。
確かに、ほとんどの細胞が互いに影響しないという事実を考慮して、有効な以前のグリッドの総数を見つける方法がありますか？
ほとんどの場合、完全な解決策のコードではなく、アプローチに対する理解が求められます。ご希望の場合は先に進んでください。