TopCoder, Single Round Match 655, Divisino 1, Level 1 : BichromePainting

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13709&rd=16415

問題概要

　グリッド状の盤面に色を塗る．盤面上のセルは最初，全て白に塗られている．可能な操作は，与えられた整数 について， の矩形領域を任意に選択して，その内部全体を白または黒のどちらかの一色で塗る操作である．
　最終的に作りたい盤面の状態を表す文字列配列 が与えられる． が 'W' のとき，位置 のセルは白く塗られなければならず，'B' ならば黒に塗られなければならない．達成可能か否か，求めよ．

解法

　 の高さを ，幅を と書きます．
　盤面を塗る手順というのはかなり多くの種類があるので，普通に探索しようとすると到底扱えません．そこで，操作の逆順を考えてみます（かなり唐突でアレですが，ひらめき勝負ってことで……）．
　 中に， の矩形領域であって単一色からなる部分があったとき，その部分は最後に塗られた（可能性がある）と考えます．そうすると，その部分が最後に塗られる前の時点では，その部分の内部はどのように彩色されていても問題が無いということになります（ちなみに，そのような領域がオーバーラップの有無を問わず複数あったとしても，それらを塗る順番が多少変わるだけで同じことが言えます）．この何色でもよいという状態を，文字 '?' で表すとします．'?' がある状態の盤面についても同じように考えてみると，'?' と他の高々一色からなる 領域は，同様に全部 '?' に変えてしまえることが分かります．この操作を '?' が増えなくなるまで繰り返し適用したとします．そうしたときに，盤面全体が '?' になっていれば，適当な手順で操作をすることで を作ることができます．そうでないとき， を作ることはできません．一瞬，「'W' が残る分には大丈夫ではないか？」と思えますが，'W' が残るということは，その 'W' を '?' に変えられなくするような位置に 'B' が残っているということなので，ダメです．
　計算量ですが， 領域の取り方が 通りあって，ある領域が条件を満たすか否かの判定に 時間かかります．また，一回塗りつぶす毎に '?' でないセルが 1 つ以上減るので，塗りつぶす操作の発生回数もまた 回です．従って，全体は 時間となります．

コード

using VS = vector< string >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )

const string colors = "WB";

class BichromePainting
{
public:
	int H, W;
	int k;

	string isThatPossible( vector <string> board, int k )
	{
		H = SZ( board ), W = SZ( board[0] );
		this->k = k;

		while ( backpaint( board ) );
		return all_of( ALL( board ), [=]( const string &row ){ return count( ALL( row ), '?' ) == W; } ) ? "Possible" : "Impossible";
	}

	bool backpaint( VS &board )
	{
		REP( i, H - k + 1 )
		{
			REP( j, W - k + 1 )
			{
				FOR( c, colors )
				{
					if ( ok( board, i, j, c ) )
					{
						REP( dy, 0, k )
						{
							REP( dx, 0, k )
							{
								board[ i + dy ][ j + dx ] = '?';
							}
						}
						return true;
					}
				}
			}
		}

		return false;
	}

	bool ok( const VS &board, const int y, const int x, const char color )
	{
		bool found = false;
		REP( dy, 0, k )
		{
			REP( dx, 0, k )
			{
				const char c = board[ y + dy ][ x + dx ];

				if ( c != '?' && c != color )
				{
					return false;
				}

				found |= c == color;
			}
		}

		return found;
	}
};