Codeforces #168 Div2 B "Convex Shape"
問題
黒または白に塗られているN×Mのマス目がある。
黒のマス=移動可能 白のマス=壁(移動不可能)
隣の上下左右の黒マスに移動できる。
任意の2つの黒のマスにおいて、曲がる回数を一回までに限定して
行ったりきたり出来ちゃう場合は"YES"を
そうでない場合は"NO"を出力せよ。
制約
1 <= N,M <= 50
解法
2つの黒マスを選んで
実際にマスを辿ってみた。
ソース
const int MAX_HW = 50; int W, H; bool isW[MAX_HW][MAX_HW]; int main() { istream& in = cin; in >> H >> W; for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ char c; in >> c; isW[y][x] = (c == 'W' ? true : false); } } bool res = true; for( int y1 = 0; y1 < H; y1++ ) for( int x1 = 0; x1 < W; x1++ ) for( int y2 = 0; y2 < H; y2++ ) for( int x2 = 0; x2 < W; x2++ ){ if( isW[y1][x1] || isW[y2][x2] ) continue; // 左上から右下へとマス目に順序をつけて、 // 1つ目 < 2つ目をチェックするようにする if( y1 * W + x1 >= y2 * W + x2 ) continue; int lx = x1, ly = y1, hx = x2, hy = y2; if( x1 > x2 ){ lx = x2; hx = x1; } // 2つの黒マスを対角線とした長方形を見立てて、 // その上辺・下辺・左辺・右辺にあたるマス目が通行可能かどうか bool u = true, b = true, l = true, r = true; for( int i = lx; i <= hx; i++ ) if( isW[ly][i] ) u = false; for( int i = lx; i <= hx; i++ ) if( isW[hy][i] ) b = false; for( int i = ly; i <= hy; i++ ) if( isW[i][lx] ) l = false; for( int i = ly; i <= hy; i++ ) if( isW[i][hx] ) r = false; // 1つ目のy <= 2つ目のyだから・・・ if( x1 < x2 ){ // 2つ目の黒マスのx座標が1つ目より大きければ // 上右か下左のどちらかが通行可能ならおk res &= ( u && r ) || ( b && l ); }else{ // 2つ目の黒マスのx座標が1つ目より小さければ // 上左か下右のどちらかが通行可能ならおk res &= ( u && l ) || ( b && r ); } } cout << (res ? "YES" : "NO") << endl; }