H - Grid 1

キーワード

• DP
• EDPC

解説

問題 (opens in a new tab)

$i=0,1,\dots,H-1, ~ j=0,1,\dots,W-1$ に対して、 $dp_{i,j}$ を次のように定義する。

$(0,0)$ から $(i,j)$ に至る最短路の数

$dp_{0,0} = 1$ とする。

スタートが $(0,0)$ でゴールが $(H-1,W-1)$ であることから、最短路は右か下にしか進めない。つまり、 $(i,j)$ へは、 $(i-1,j)$ または $(i,j-1)$ からしか行けない。

よって、 $(i,j)$ に行く通りは、 $(i-1,j)$ または $(i,j-1)$ に行く通りの和に等しいことがわかる。

従って、次の漸化式が成り立つ。

問題から、 $(i,j)$ が壁の時は通れないことがわかるので、壁の時は $dp_{i,j} = 0$ とする。

計算量は $O(HW)$ となる。

最終的な答えは $dp_{H-1,W-1}$ となる。

提出コード

int main() {
    int h, w; cin >> h >> w;
    vector<string> A(h); rep(i, 0, h) cin >> A[i];
    vector<vector<ll>> dp(h, vector<ll>(w, 0));
    dp[0][0] = 1;
    rep(i, 0, h) rep(j, 0, w) {
        if (i+1 < h && A[i+1][j] == '.') {
            dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= 1000000007;
        }
        if (j+1 < w && A[i][j+1] == '.'){
            dp[i][j+1] += dp[i][j];
            dp[i][j+1] %= 1000000007;
        }
    }
    cout << dp[h-1][w-1] << endl;
}