WARush

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

Codeforces #192 Div2 C "Purification"

問題

http://codeforces.com/contest/330/problem/C

あなたは悪魔神殿を探索している冒険者である。最弱のゾンビのカップルとの戦いに敗れた後、n * nの四角いマスでできた部屋であなたは生き返った。行は上から下へと1からnの番号が振られ、列は左から右へと1からnの番号が振られている。部屋の一角には出口につながるドアがあったが、そこは悪魔の魔術によって封印されている。ドアの傍らにはこんな碑文が書かれていた。

全ての悪を浄化せよ、さすればドアは開かれよう!

ベテラン冒険者のあなたは即座に何をすればよいか悟った。あなたは全てのマスに、悪のパワーが宿っている事に気付いた。全てのマスを浄化する必要がある。

マスを浄化するただひとつの方法はスペル「浄化」を使用する事である。あなたは1つのマスを選び、このスペルを使用すると、選んだマスと同じ行と、同じ列のマス全てを浄化できる。スペル「浄化」は複数回使うことができる。

あなたはなるべくスペル「浄化」を唱える回数を少なくしてn * nの全てのマスを浄化したい。簡単なことのように聞こえるが、いくつかのマスは悪のパワーが濃い事に注意されたい。あなたはスペル「浄化」を、濃い悪のパワーが篭っているマスを選んで唱えることができない。

n * nのマス全てを浄化するのに最小の詠唱回数を出力せよ。

制約

1 <= n <= 100




考えた事

こういうときは縦に詠唱していく

...E..
...E..
...E..
...E..
...E..
...E..

こういうときは横に詠唱していく

......
......
EEEEEE
......
......
......

こういうときはGAME OVER
ゾンビになって一生を終える

...E..
...E..
EEEEEE
...E..
...E..
...E..

ソースコード

int N;
vector<string> field;

int main() {
    cin >> N;
    for( int i = 0; i < N; i++ ){
        string line;
        cin >> line;
        field.push_back( line );
    }

    // 縦でやってけない?
    bool ok = true;
    for( int y = 0; y < N; y++ ){
        bool line_ok = false;
        for( int x = 0; x < N; x++ ){
            if( field[y][x] == '.' ) line_ok = true;
        }
        ok &= line_ok;
    }

    // 縦でやってこう
    if( ok ){
        for( int y = 0; y < N; y++ ){
            for( int x = 0; x < N; x++ ){
                if( field[y][x] == '.' ){
                    printf( "%d %d\n", y+1, x+1 );
                    break;
                }
            }
        }
        return 0;
    }

    // 横でやってけない?
    ok = true;
    for( int x = 0; x < N; x++ ){
        bool line_ok = false;
        for( int y = 0; y < N; y++ ){
            if( field[y][x] == '.' ) line_ok = true;
        }
        ok &= line_ok;
    }

    // 横でやってこう
    if( ok ){
        for( int x = 0; x < N; x++ ){
            for( int y = 0; y < N; y++ ){
                if( field[y][x] == '.' ){
                    printf( "%d %d\n", y+1, x+1 );
                    break;
                }
            }
        }
        return 0;
    }

    // GAME OVER
    cout << -1 << endl;
}