Codeforces #202 Div1. D. Turtles

これ、本番はわからなかったのだが、あるLemmaを使うとあっさり解ける、ということで試してみた。
http://codeforces.com/contest/348/problem/D

問題

NxMのグリッドが与えられる。一部のグリッドは移動不可である。
ここで、2匹のカメが左上のマスから右下のマスに1マスずつ最短経路で移動する。
この時、2匹のカメが最初と最後のマス以外で重ならないような移動手順の組み合わせの数を答えよ。

解法

Lindström–Gessel–Viennot lemma - Wikipedia, the free encyclopedia
Lindström-Gessel-Viennot lemma - うどん記

そのまんまの問題である。
2匹のカメの1手目の移動先である(0,1)(1,0)から、最後の1手前の移動先である(N-2,M-1)(N-1,M-2)の2x2の組み合わせの移動経路を求め、その4要素からなる2x2行列の行列式を求めればよい。

int H,W;
int dpdp[3010][3010];
string S[3000];
ll mo=1000000007;

void dodo(int sx,int sy) {
	int i,x,y;
	ZERO(dpdp);
	if(S[sy][sx]=='.') dpdp[sx][sy]=1;
	FOR(y,H) FOR(x,W) if(dpdp[x][y]) {
		if(x<W-1 && S[y][x+1]=='.') {
			dpdp[x+1][y] += dpdp[x][y];
			if(dpdp[x+1][y] >= mo) dpdp[x+1][y] -= mo;
		}
		if(y<H-1 && S[y+1][x]=='.') {
			dpdp[x][y+1] += dpdp[x][y];
			if(dpdp[x][y+1] >= mo) dpdp[x][y+1] -= mo;
		}
	}
}

void solve() {
	int f,i,j,k,x,y,z,tx,ty;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	dodo(1,0);
	ll A=dpdp[W-2][H-1];
	ll B=dpdp[W-1][H-2];
	dodo(0,1);
	ll C=dpdp[W-2][H-1];
	ll D=dpdp[W-1][H-2];
	cout << (((B*C-A*D)%mo)+mo)%mo << endl;
}

まとめ

知っていればあっさり、知らないと難しい問題。