SRM578 Div2 Medium "GooseInZooDivTwo"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12545
訳
カラスのキースは動物園のガチョウのケージを覗いている。
そのケージの床は正方形のマスで区切られている。
何羽かの鳥がそのマスで羽を休めている。(1マスにつき多くても1羽である)
彼らのうち何羽かがガチョウであり、その他はアヒルである。
キースはどの鳥がガチョウであるかを知りたい。
キースは次のような事を知っていた。
- ケージには少なくとも1羽はガチョウがいる。
- あるガチョウからマンハッタン距離でdist以内にいる鳥もまたガチョウである
あなたには文字列配列fieldとdistが与えられる。
fieldはケージの床の状態を表している。
各文字列の各文字は、1つのマスに対応している。
この文字は以下のような意味である。
- 'v'という文字は、そのマスに鳥がいることを表している。
- '.'という文字は、そのマスは何も無いことを表している。
ケージのガチョウの配置の仕方が何パターンあるかを返せ。
テストケースには、パターンが存在し得ないものがあることに注意せよ。
制約
1 <= マスの幅、高さ <= 50
1 <= dist <= 100
考えた事
このマスにガチョウがいたら、ガチョウがいなきゃいけないマスがでてくるはず。
そんなマス同士をグループとして、グループ数を数える。
各グループにおいて、ガチョウを配置する・しないの2通りがあり、
全てのグループに配置しない事はできないため、
2^グループ数 - 1が答え
vが一個も無ければそのテストケースはおかしいから0
実装中
距離がdistと同じマスをグループとして数え上げるよ!!
事後
dist以内!以内!以内!以内!以内!
ソースコード
const int MOD = 1000000007; class GooseInZooDivTwo { public: int H, W; vector<string> F; bool chk[55][55]; int dist; // (x y) (nx, ny)のマンハッタン距離 int getDist( int x, int y, int nx, int ny ){ return abs( x - nx ) + abs( y - ny ); } // (x, y)から距離dist以内のvにチェックを付けてく void dfs_chk( int x, int y ){ for( int ny = 0; ny < H; ny++ ){ for( int nx = 0; nx < W; nx++ ){ if( F[ny][nx] != 'v' || chk[ny][nx] ) continue; if( dist < getDist( x, y, nx, ny ) ) continue; chk[ny][nx] = true; dfs_chk( nx, ny ); } } } int count(vector <string> field, int _dist){ F = field; H = field.size(); W = field[0].length(); dist = _dist; int cnt = 0; // グループ数 memset( chk, false, sizeof(chk) ); for( int y = 0; y < H; y++ ){ for( int x = 0; x < W; x++ ){ if( F[y][x] != 'v' || chk[y][x] ) continue; cnt++; chk[y][x] = true; dfs_chk( x, y ); } } if( cnt == 0 ){ return 0; // おかしいよ! } long long res = 1; for( int i = 0; i < cnt; i++ ){ res = (res * 2) % MOD; } return (int)(res - 1); } };