SRM655 div1 250

とぷこだ

さぼってるからできるようにならない。

問題

N*Nのセルが与えられる。
各セルにはBまたはWが書かれている。
各セルがすべてWの状態から初めて、K*Kの正方形の形でBまたはWで塗りつぶすことを繰り返し、与えられたセルの状態にすることができるか、できないかを答える。

K<=N<20

考え方

すべてWの状態から塗りつぶしを何回か行って行ったものであるならば、最終状態では塗りつぶしを最後に行ったK*Kの正方形セルが存在するはず。
もし、それが存在する場合は、塗りつぶすセルの塗りつぶす前は何でもよい(「*」などにしておく)。
同様に、最終状態から1つ前の上記の状態でも、塗りつぶしを行ったK*Kの正方形セルが存在するはずである。
これを繰り返し、すべて「*」の状態(Possible)、または、途中で正方形セルが見つからなくなったら(Impossible)、と判定できる。

反省

セル単位で見てしまっていて、「そのセルを左端とするK*Kの正方形に塗りつぶすか、塗りつぶさないか」の2通りをすべて確認する、という風に考えてしまって、前方向から全通り(当たり前にTLEなのに、提出しちゃった)試すか、メモ化再帰か(状態はどうやって持つ？)みたいな感じで考えてしまっていた。。。


スタート状態から操作を繰り返してゴール状態になるような時、それをゴール状態から逆順にすることで、求められないか？は以前教えてもらったりしてたのに、、、、
http://d.hatena.ne.jp/phyllo_algo/20150120/1421776480