TopCoder SRM 655 Div1 Easy BichromePainting

EasyもMediumも遅かったけど、Easyの難易度が高かったことと2Challenge成功のおかげで結構良い順位に。
おかげでHighest更新しました。最近CFとARCが下がり気味だったので少し持ち直したね。
http://community.topcoder.com/stat?c=problem_statement&pm=13709

問題

N*Nのグリッドがあり、初期状態では全セル白である。
これらのグリッドのうちK*Kの領域を白または黒で塗りつぶす、という処理を任意の位置に任意の回数行える。

グリッドの最終状態における色が与えられる。
そのような塗り分けができるか判定せよ。

解法

グリッドの最終状態から巻き戻していく。
最終的なグリッドの状態に対してK*Kの領域を総当たりする。

もしあるK*Kの領域が白か黒どちらか片方の色だけだったら、それまでの過程が何であれ最終的にそのK*K領域を目的の色で塗りつぶすことが可能となる。
なので、そのようなK*Kはどちらの色でも良いという意味で'?'など白黒以外の文字に置き換えてしまおう。
以後、同様に「白と？だけ」もしくは「黒と？だけ」のK*K領域を求めて繰り返し"?"に置き換えていけば良い。

全セル"?"に置き換え可能ならば、ここまで"?"に置き換えた作業を逆向きに行えば最終状態を再現できることになるので判定は「塗り分け可能」となる。

class BichromePainting {
	public:
	
	string isThatPossible(vector <string> S, int K) {
		int N=S.size();
		int x,y,ty,tx;
		
		bool up=true;
		while(up) {
			up=false;
			FOR(y,N) FOR(x,N) if(y+K-1<N && x+K-1<N) {
				int w=0,b=0;
				FOR(ty,K) FOR(tx,K) {
					if(S[ty+y][tx+x]=='W') w++;
					if(S[ty+y][tx+x]=='B') b++;
				}
				if(w&&b) continue;
				if(w==0 && b==0) continue;
				FOR(ty,K) FOR(tx,K) S[ty+y][tx+x]='?';
				up=true;
			}
		}
		FOR(y,N) FOR(x,N) if(S[y][x]!='?') return "Impossible";
		return "Possible";
	}
}

まとめ

本番かなり手間取った。
端から塗りつぶすことも試したがサンプル合わないし。
幸い、Nの上限からO(N^4)じゃなくO(N^6)である解が要求されることがわかり、なんとかこの解法にたどり着けた。