[USACO08MAR] Cow Travelling S - dp

给定一个 \(N\times M\) 的网格，有些格子是障碍，求走 \(T\) 步，从 \((R_1,C_1)\) 走到 \((R_2,C_2)\) 的方案数

Solution

难度：L2

暴力 DP，设 \(f[t][i][j]\) 表示走了 \(t\) 步，从起点走到 \((i,j)\) 的方案数，暴力转移即可。

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

#define int long long

int n,m,T,f[20][105][105],r1,c1,r2,c2;
char s[105][105];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>m>>T;
    for(int i=1;i<=n;i++) {
        cin>>s[i]+1;
    }
    cin>>r1>>c1>>r2>>c2;
    f[0][r1][c1]=1;
    for(int t=1;t<=T;t++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(s[i][j]=='.') {
                    f[t][i][j]+=f[t-1][i][j-1];
                    f[t][i][j]+=f[t-1][i][j+1];
                    f[t][i][j]+=f[t-1][i-1][j];
                    f[t][i][j]+=f[t-1][i+1][j];
                }
            }
        }
    }
    cout<<f[T][r2][c2];
}

[USACO08MAR] Cow Travelling S - dp

原文：https://www.cnblogs.com/mollnn/p/12490441.html