グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。

• 問題へのリンク

問題概要

のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。

左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、壁マスに入ることなく到達する経路の本数を数えよ。

制約

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> C(H);
    for (int i = 0; i < H; i++) cin >> C[i];

    vector dp(H, vector(W, 0LL));
    dp[0][0] = 1;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
        if (C[i][j] == '#') continue;
        if (i-1 >= 0) dp[i][j] += dp[i-1][j];
        if (j-1 >= 0) dp[i][j] += dp[i][j-1];
    }
    cout << dp[H-1][W-1] << endl;
}