WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}