TopCoder SRM 578, Division 1, Level 1 : GooseInZooDivOne

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12539&rd=15498

概要

グリッド状のケージの中に何羽かの鳥がいる。
グリッドは文字列の配列で表され、文字が 'v' のところには一羽の鳥がおり、'.' のところにはいない。
鳥はガチョウとアヒルの二種類がいて、次の条件を満たす

• ケージの中には一羽以上のガチョウがいる
• ガチョウの数は偶数である
• いずれかのガチョウとマンハッタン距離が dist 以下の全ての鳥はガチョウである

鳥の配置として可能なものの総数を求めよ。

解法

マンハッタン距離が dist 以下の鳥のペアをグループ化していくことを考えます。
このとき、一羽の鳥はちょうど一つのグループに属します。
ある鳥をガチョウと決めると、同じグループに属する鳥は全てガチョウになります。
前処理として、鳥のグループを（ DFS｜BFS｜UnionFind木）で求め、このグループ数を N とします。
また各グループについて、属する鳥の数も求めておき、
　groups[i] := i 番のグループに属する鳥の数
としておきます。

dp[ 考慮したグループ数 ][ ガチョウの数 ] := 場合の数
として DP をします。
状態遷移は以下の二つです。

• 現在のグループをアヒルにする -> dp[ i ][ j ] から dp[ i + 1 ][ j ] を更新
• 現在のグループをガチョウにする -> dp[ i ][ j ] から dp[ i + 1 ][ j + groups[ i ] ] を更新

最後に、dp[ N ][ { x | x = { 2, 4, 8 ... } } ] の総和をとったものが答えになります。

コード

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

const int MOD = 1000000007;

typedef vector<LL> VL;
typedef vector<VL> VVL;

class GooseInZooDivOne
{
public:
	int H, W, dist;
	VS board;

	int count( vector <string> field, int dist )
	{
		this -> board = field;
		this -> dist = dist;
		this -> H = field.size();
		this -> W = field[0].size();
		
		int numv = 0;
		REP( i, 0, H )
		{
			numv += std::count( ALL( board[i] ), 'v' );
		}

		VI groups;
		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] == '.' )
				{
					continue;
				}
				groups.PB( dfs( i, j ) );
			}
		}

		const int N = groups.size();
		VVL dp( N + 1, VL( H * W + 1, 0 ) );
		dp[0][0] = 1;
		REP( i, 0, N )
		{
			REP( j, 0, dp[i].size() )
			{
				dp[i][j] %= MOD;
				dp[ i + 1 ][j] += dp[i][j];
				if ( j + groups[i] <= dp[i].size() )
				{
					dp[ i + 1 ][ j + groups[i] ] += dp[i][j];
				}
			}
		}

		LL res = 0;
		for ( int i = 2; i < dp[N].size(); i += 2 )
		{
			res += dp[N][i];
			res %= MOD;
		}

		return res;
	}

	int dfs( int y, int x )
	{
		if ( !inside( y, x ) || board[y][x] == '.' )
		{
			return 0;
		}

		board[y][x] = '.';
		int res = 1;

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( abs( i - y ) + abs( j - x ) <= dist )
				{
					res += dfs( i, j );
				}
			}
		}

		return res;
	}

	bool inside( int y, int x )
	{
		return 0 <= y && y < H && 0 <= x && x < W;
	}
};