AtCoder ABC #183 : E - Queen on Grid

いつもより簡単っぽい。
https://atcoder.jp/contests/abc183/tasks/abc183_e

問題

H*Wのグリッドが与えられる。
一部のセルは通過禁止である。
左上マスにコマが置いてあり、1手で、右・下・右下いずれかの方向に、通過禁止マスを通らない範囲で移動できるものとする。
右下マスに移動する手順は何通りか。

解法

各マスに至る到達経路をDPで数え上げて行く。
各行・列・斜めのラインにおいて、同じラインのうち最後の通過禁止マス以降に到達可能なマスの経路数の総和をそれぞれ取っておけば、1マスあたりO(1)で数え上げることができる。

int H,W;
string S[2020];
ll R[2020],C[2020],X[4020];
ll dp[2020][2020];
const ll mo=1000000007;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	FOR(y,H) FOR(x,W) {
		if(y==0&&x==0) {
			dp[y][x]=1;
		}
		else {
			dp[y][x]=(R[y]+C[x]+X[y-x+2000])%mo;
		}
		
		if(S[y][x]=='#') {
			dp[y][x]=R[y]=C[x]=X[y-x+2000]=0;
		}
		else {
			(R[y]+=dp[y][x])%=mo;
			(C[x]+=dp[y][x])%=mo;
			(X[y-x+2000]+=dp[y][x])%=mo;
		}
		
	}
	cout<<dp[H-1][W-1]<<endl;
	
}

まとめ

Dは最初水を貯められるバージョンを考えてしまいちょっと手間取った。