TopCoder SRM 578 Div1 Easy GooseInZooDivOne

問題

hxwのグリッドがある。各セルは、なにもない'.'か'v'鳥がいるかのどちらか。
鳥は二種類A, Bがいて、任意のセルの鳥について、そこからマンハッタン距離でd以下にいるセルの鳥は、全て同じ種類である。

また種類Aの鳥は一羽以上、かつ偶数羽いる。
グリッドおよびdが与えられるとき、各セルの鳥の種類の与え方は何通りあるか、
mod 1000000007で求めよ。

制約条件

h, w≦50

方針

union-findを使って、
マンハッタン距離d以内にいる鳥同士をunionでくっつける。

そしたらナップサック的なDPをしてもいいし、
奇数羽の塊がx個あるとすると、そのうち偶数個を種類Aに振り分ける場合の数は、
(2^x) / 2 = 2^x-1通りになるので、そうやって計算してもいい。

public class GooseInZooDivOne {

    char[][] map;
    int d, h, w;
    long mod = 1000000007;

	public int count(String[] field, int dist) {

        h = field.length;
        w = field[0].length();
        d = dist;
        map = new char[h][w];
        for(int i=0; i<h; i++) map[i] = field[i].toCharArray();

        int even = 0, odd = 0;
        for(int i=0; i<h; i++){
            for(int j=0; j<w; j++){
                if(map[i][j]=='v'){
                    int num = bfs(i, j);
                    if(num%2==0) even++;
                    else odd++;
                }
            }
        }
		long ans = 0;
        for(int i=0; i<even; i++){
            if(ans==0) ans = 1;
            ans = (ans * 2)%mod;
        }
        for(int i=0; i<odd-1; i++){
            if(ans==0) ans = 1;
            ans = (ans * 2)%mod;
        }
        return (int)Math.max(ans-1, 0);
	}

    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    int bfs(int sy, int sx){
        LinkedList<int[]> list = new LinkedList<int[]>();
        list.add(new int[]{sx, sy, 0});
        int cnt = 0;
        int[][] v = new int[h][w];

    	for(int i = 0; i < h; i++)
    		for(int j = 0; j < w; j++) v[i][j] = 1000000;
    	
    	
        while(list.size()>0){
            int[] q = list.poll();
            int x = q[0], y = q[1], dist = q[2];

            if(map[y][x]=='v'){
                map[y][x] = '.';
                cnt++; 
                dist = 0;
            }
            if(dist>=d || dist >= v[y][x]) continue;
            v[y][x] = dist;

            for(int i=0; i<4; i++){
                int nx = x + dx[i], ny = y + dy[i];
                if(nx<0 || nx>=w || ny<0 || ny>=h) continue;
                list.add(new int[]{nx, ny, dist + 1});
            }
        }

        return cnt;
    }
}