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