torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, Single Round Match 655, Division 2, Level 1 : BichromeBoard

問題概要

 グリッド状の盤面がある.この盤面の各セルを白または黒に塗る.いくつかのセルについては塗る色が決まっているが,色が決まっていないセルもある.
 塗り方の情報は文字列の配列 board で与えられる.ij 列のセルを ( i, j ) と表すとするとき,( i, j ) の塗り方は,board_{ ij } の文字によって,

  • 'W' -> 白に塗る
  • 'B' -> 黒に塗る
  • '?' -> 決まっていない

となる.
 追加の制約として,辺を接する 2 つのセルを同じ色に塗ることはできない.条件を満たす塗り方は存在するか?

解法

 隣接するセルの色に関する制約から,妥当な彩色は必ず 市松模様 となっています.左上のセルを白にするか黒にするかで 2 通りの彩色が考えられますが,たった 2 通りなので実際に生成して,どちらかが board とマッチするかどうかを判定することで問題を解くことができます.
 「マッチする」とは,生成した彩色を t としたとき,全てのセルについて board[ i ][ j ] != '?' && board[ i ][ j ] != t[ i ][ j ] が成り立たないこととします.この式が真となるセルが 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 SZ( v ) ( (int)( v ).size() )

constexpr char colors[] = "WB";

class BichromeBoard
{
public:
	int H, W;

	string ableToDraw( vector <string> board )
	{
		H = SZ( board ), W = SZ( board[0] );

		VS t1( H, string( W, ' ' ) ), t2 = t1;
		REP( i, H )
		{
			REP( j, W )
			{
				const int odd = ( i + j ) % 2;
				t1[i][j] = colors[ odd ];
				t2[i][j] = colors[ 1 - odd ];
			}
		}
		
		return match( board, t1 ) || match( board, t2 ) ? "Possible" : "Impossible";
	}

	bool match( const VS &s, const VS &t )
	{
		REP( i, H )
		{
			REP( j, W )
			{
				if ( s[i][j] != '?' && s[i][j] != t[i][j] )
				{
					return false;
				}
			}
		}
		return true;
	}
};