本選課題 [ライフゲーム]

SuperCon'99 本選課題 [ライフゲーム]

SuperCon'99 実行委員会

ライフゲームの規則

ライフゲームの宇宙は碁盤のようにマス目が並んだものである。そのマス目は「セル」と呼ばれ、一つの「生命」の存在場所と考える。セルは、生命の2つの状態(生と死）に応じて、2つの状態をとる。

生死
セルの状態 ■ □

	生	死
セルの状態	■	□

宇宙の進化は、0以上の整数により表現される時刻(最初は時刻0で、次は時刻1、時刻2、...というような時刻)に従って進んでいく。時刻t+1におけるセルの状態は、時刻tの状態と、そのセルを取り囲む8つ(東、西、南、北、北東、南東、北西、および南西)のセルの状態に依存して決定される。

セルの現在の状態周囲の■セルの数セルの次の状態
■ 2もしくは3 ■
それ以外 □
□ 3 ■
それ以外 □

セルの現在の状態	周囲の■セルの数	セルの次の状態
■	2もしくは3	■
それ以外	□
□	3	■
それ以外	□


[例1](宇宙のサイズ=3)
   □ □ ■      □ ■ □
   ■ ■ □  →  □ ■ □
   □ □ □      □ □ □ 

[例2](宇宙のサイズ=5)
   □□□□□    □□□□□
   ■□□□□    □■□□□
   ■□■□□ → □■□□□
   □□□■□    □■■■□
   ■□□■□    □□□□□

時刻tの宇宙の状態を、時刻t+1の宇宙の状態に変更する際は、それぞれのセルに関し、いったん次の状態を計算しておき、それがすべて済んだ状態で「同時に」に宇宙全体を新しい状態に書き直す。
ライフゲームの宇宙は有限とする。
境界付近におけるセルの状態のあつかいは、その他の場所とまったく同じである。つまり、着目したセルの周囲に存在するセルの個数と状態に依存する。

初期セルパターンの定義

初期セルパターンは、次の4つの展開規則、 1)東へ展開(eと表記)、 2)西へ展開(w)、 3)南へ展開(s)、 4)北へ展開(n)、を組み合わせることによって得られるセル配置を指す。次に規則を適用する始点セルを[■]で区別する。ここで、展開の深さとは、これら4つの規則を順に適用した回数を指す。この生成規則はライフゲームの規則とは無関係である。


[規則e]                      [規則w]
[■] --e--> ■                            [■]■
              ■ [■]        [■] --w-->        ■

[規則s]                      [規則n]
[■]  --s-->   ■                          [■]
             ■                             ■                      
            [■]             [■]  --n--> ■

例) 深さ3の生成規則列 n w s によって作られる初期セルパターン。■以外のセルは、すべて、□とする。


     □□□□□□
     □□■■□□
     □■□□■□
     □■□□■□
     □□□■□□
           ↑原点

問題

宇宙はサイズ奇数の正方形とし、宇宙の中央に初期パターン生成の原点を置く。ついで、初期セルパターンの生成規則に従い、指定された深さのパターンを生成する。この時点を時刻0とする。ライフゲームの規則を適用し、与えられた時刻Nに、一つ以上生存状態のセル■が残る初期セルパターン生成規則列の数を求める。

プログラムへの入力は次の通り。

宇宙のサイズ
初期セルパターンの深さ
最終時刻N

また、出力は次の通り。

初期セルパターン生成規則列の個数