CODE FESTIVAL 2014 上海 : G - Ammunition Dumps

問題文の読解が難しい。
http://code-festival-2014-china-open.contest.atcoder.jp/tasks/code_festival_china_g

問題

R*Cの２次元グリッドがある。
幾つかのセルに爆弾が置いてあり、かつ最初に火をつける爆弾が指定される。

爆弾は一度火をつけられると、以後任意のタイミングで爆発させることができる。
爆弾は爆発すると四方に炎が飛び、四方の(他の爆弾が壁とならない)爆弾に引火する。
一度爆発した爆弾は再度引火・爆発することはないが、炎に対する壁としての効果は残る。

グリッド上すべての爆弾が引火するケースにおいて、各爆弾の最初の引火元の組み合わせ数を求めよ。

解法

最初自分は爆発順の組み合わせ数を求めるのかと思って混乱していたが、どうも最初の引火元の組み合わせを求めるだけだった。
この問題は、全域木の組み合わせを求める問題に帰着できる。
引火元・引火先の順番性はどうなるの？と思うかもしれないが、一度全域木を作ってしまえばその木を最初に火をつける爆弾を根とする根付木と見なし、親から子に引火すると考えればよい。

まずはUnion-Findなどで全爆弾に引火可能か判定したうえで、全域木定理でラグランジュ行列の行列式を計算するだけ。

class UF {
	public:
	static const int ufmax=5052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int operator[](int x) {return (ufpar[x]==x)?(x):(ufpar[x] = operator[](ufpar[x]));}
	int count(int x) { return ufcnt[operator[](x)];}
	void unite(int x,int y) {
		x = operator[](x); y = operator[](y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

ll mo=1000000009;
UF uf;
int H,W,num;
int id[20][20];
string S[20];

ll mat[256][256];

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll det_mo(int N) {
	int x,y,z;
	ll ret=1;
	FOR(y,N) FOR(z,N) mat[y][z]=((mat[y][z]%mo)+mo)%mo;
	FOR(x,N) {
		if(mat[x][x]==0) {
			for(y=x+1;y<N;y++) if(mat[y][x]) break;
			if(y==N) return 0;
			FOR(z,N) swap(mat[x][z],mat[y][z]);
		}
		ret=ret*mat[x][x]%mo;
		ll rev=modpow(mat[x][x],mo-2,mo);
		FOR(z,N) mat[x][z]=rev*mat[x][z]%mo;
		for(y=x+1;y<N;y++) if(mat[y][x]) {
			rev=mat[y][x];
			for(z=x;z<N;z++) mat[y][z]=((mat[y][z]-mat[x][z]*rev)%mo+mo)%mo;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='W') id[y][x]=num++;
	}
	FOR(y,H) FOR(x,W) if(S[y][x]=='W') {
		FOR(i,4) {
			int dd[]={0,1,0,-1};
			int tx=x,ty=y;
			while(1) {
				tx+=dd[i];
				ty+=dd[i^1];
				if(tx<0 || tx>=W || ty<0 || ty>=H) break;
				if(S[ty][tx]=='W') {
					uf.unite(id[y][x],id[ty][tx]);
					mat[id[y][x]][id[y][x]]++;
					mat[id[y][x]][id[ty][tx]]--;
					break;
				}
			}
		}
	}
	
	if(uf.count(0)!=num) return _P("0\n");
	cout << det_mo(num-1) << endl;
}

まとめ

問題文を誤読してたら解けないわな…。