SRM 578, Division 2, Level 2 : GooseInZooDivTwo

問題文

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

概要

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

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

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

解法

基本的には Division 1, Level 1 と同一ですが、奇偶の条件が無くなっています。
この場合、各グループ毎にガチョウにするかアヒルにするかの二通りで 通りの配置があります。
そのうちの一つはガチョウの数が 0 になるので、答えは になります。

コード

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 GooseInZooDivTwo
{
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();
		LL res = 1;
		REP( i, 0, N )
		{
			res *= 2;
			res %= MOD;
		}
		
		return res - 1;
	}

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