Codeforces #168, Division 2, B : Convex Shape

問題文

http://codeforces.com/contest/275/problem/B

概要

グリッド状の盤面が白と黒の二色に塗られている。
黒が凸であるかどうかを判定せよ。
ここで「黒が凸である」とは、全ての相異なる二つの黒のグリッドの組み合わせについて、「隣接する黒のグリッドを辿って移動するとき、高々一回の方向転換で行ける」を充足する場合である。

解法

あるグリッドから別のあるグリッドへ一回の方向転換で移動する場合の経路は、着目する二点を対角とする長方形の辺上となります。
全ての黒いグリッドの組み合わせについて、この長方形状の経路を実際に辿って判定します。
（いずれかの座標が等しい場合は線分になりますが、長さ 0 の線分があると考えれば、場合分けせずに処理できます）

コード

typedef vector<string> VS;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )
#define fst first
#define snd second

const int dir[][2] = {
	1, 0,
	0, 1,
	-1, 0,
	0, -1
};

bool solve()
{	
	int h, w;
	cin >> h >> w;

	VS board( h );
	FOR( line, board )
	{
		cin >> line;
	}

	vector< PII > blacks;
	REP( i, 0, h )
	{
		REP( j, 0, w )
		{
			if ( board[i][j] == 'W' )
			{
				continue;
			}
			blacks.PB( MP( i, j ) );
		}
	}

	const int N = blacks.size();

	REP( i, 0, N )
	{
		REP( j, i + 1, N )
		{
			bool f1 = true, f2 = true;

			if ( blacks[i].snd <= blacks[j].snd )
			{
				// f1 : └ / f2 : ┐
				REP( y, blacks[i].fst, blacks[j].fst + 1 )
				{
					f1 &= board[y][ blacks[i].snd ] == 'B';
					f2 &= board[y][ blacks[j].snd ] == 'B';
				}
				REP( x, blacks[i].snd, blacks[j].snd + 1 )
				{
					f1 &= board[ blacks[j].fst ][x] == 'B';
					f2 &= board[ blacks[i].fst ][x] == 'B';
				}
			}
			else
			{
				// f1 : ┌  / f2 : ┘
				REP( y, blacks[i].fst, blacks[j].fst + 1 )
				{
					f1 &= board[y][ blacks[j].snd ] == 'B';
					f2 &= board[y][ blacks[i].snd ] == 'B';
				}
				REP( x, blacks[j].snd, blacks[i].snd + 1 )
				{
					f1 &= board[ blacks[i].fst ][x] == 'B';
					f2 &= board[ blacks[j].fst ][x] == 'B';
				}
			}

			if ( !( f1 || f2 ) )
			{
				return false;
			}
		}
	}

	return true;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	cout << ( solve() ? "YES" : "NO" ) << endl;

	return 0;
}