はまやんはまやんはまやん

hamayanhamayan's blog

Grid 1 [Educational DP Contest / DP まとめコンテスト H]

https://atcoder.jp/contests/dp/tasks/dp_h

解説

https://atcoder.jp/contests/dp/submissions/3947874

mod10^9+7の数え上げはDPの可能性が高いし、マス移動でDPを使う問題は死ぬほどみたせいか、DPの定義が自然と出てくるので解説ができない。
制約もこの定義を後押ししている。
dp[y][x] := マス(y,x)に移動する経路の組合せ
dp[y][x]からの遷移を考えるとdp[y+1][x]かdp[y][x+1]がある。
この2つについて、枠内でかつ空マスであるときに遷移を行う。
 
mod10^9+7の扱いは、自分はmintを使っている。
たまに自力で書きたい場面が出てきたりするので、中身がわかってるとなお良し。

int H, W; string A[1010];
mint dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> A[y];
 
    dp[0][0] = 1;
    rep(y, 0, H) rep(x, 0, W) {
        if (y + 1 < H and A[y + 1][x] != '#') dp[y + 1][x] += dp[y][x];
        if (x + 1 < W and A[y][x + 1] != '#') dp[y][x + 1] += dp[y][x];
    }
    cout << dp[H - 1][W - 1] << endl;
}