WARush

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

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