AOJ 1304 Infected Land

ICPC 2009 東京予選 Problem J

問題概要

n×n（n≦5）セルのライフゲームのセル全て死滅させるのにかかる最小ターン数を求める。ライフゲームのルールは通常と同じである。すなわち、

• ターン開始時に、生物のセルについて、周囲8セルのうち、2つまたは3つが生物の

セルの場合その生物は生き残る

• ターン開始時に、死滅しているセルについて、周囲8セルのうち丁度3つが生物のセルの場合ターン終了時にそのセルに生物が生まれる
• それ以外の場合セルは死滅する（or死滅したままである）

フィールドの中には１台の防疫車があり、これについては特別に次のようなルールを適用する。

• 毎ターンの最初に防疫車は周囲8セルのうち、生物のいないセルどれかを選び「必ず」移動する。
• 防疫車のいるセルはターン終了時に生物が生まれることはない
• あるセルが周囲8セルのうち生物のセルを数える時、防疫車のいるセルは生物のセルとして数える

解法

状態数は最大でも25*2^25（≒8億）と小さいので幅優先で書くだけ。枝刈りなどはせずに通る。
ただし、探索済みの状態を保存するためのキーにvectorを使ったりなどあんまり効率の悪いことをやるとダメ（だと思う。試してない）
状態数が8億しかないのでint型のハッシュ値を作るのが自然な発想。