DPまとめコンテスト H - Grid 1

H - Grid 1

概要

のグリッドがある。このグリッドは空マス.か壁#のいずれかで構成される。
左上のマスから、右・下への移動のみを繰り返し、かつ空マスのみを通りながら右下のマスに移動する。
このとき、移動方法の場合の数を求めよ。（mod で出力する）

制約

方針

dp[i][j] : i-1, j-1のマスに行く経路の場合の数 としてDPする。

解答

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
ll MOD = 1e9 + 7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int h, w;
	cin >> h >> w;
 
	string a[h];
	rep(i, h) cin >> a[i];
 
	ll dp[h][w];
	// dp[i][j] : i-1, j-1のマスに行く経路の場合の数
	rep(i, h) rep(j, w) dp[i][j] = 0;
	dp[0][0] = 1;
 
	for(int i = 0; i < h; i++){
		for(int j = 0; j < w; j++){
			if((i == 0 && j == 0) || a[i][j] == '#') continue;
 
			if(i-1 >= 0){
				dp[i][j] += dp[i-1][j];
				dp[i][j] %= MOD;
			}
 
			if(j-1 >= 0){
				dp[i][j] += dp[i][j-1];
				dp[i][j] %= MOD;
			}
		}
	}
 
	cout << dp[h-1][w-1] << endl;
}