能量场·题解

思路：

有一个 $N*M$ 的地图，.可以走，*不可以走。我们一开始在（$R_1$，$C_1$），需要在正好第 $T$ 步到达（$R_2$，$C_2$），输出所有可行的路径数量，答案对 $998244353$ 取模。

输入后先把dp数组的第0步时的第 $R_1$ 列 $C_1$行设置为1，因为一开始在这里，随后迭代 $T$ 次，输出 dp数组的第 $T$ 步时的第 $R_2$ 列 $C_2$行 就行。

---

代码：

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

const int MOD=998244353;
int n,m,t,r1,c1,r2,c2;
long long dp[110][110][210];
char map_[110][110];

int main(){
    cin>>n>>m>>t;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>map_[i][j];
    cin>>r1>>c1>>r2>>c2;
    r1--,c1--,r2--,c2--; 四行都是输入
    dp[r1][c1][0]=1; 初始状态设置

    for(int tt=1;tt<=t;tt++){ 迭代T回合
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(map_[i][j]=='*') continue; *走不了，忽略
                if(i>0) dp[i][j][tt]=(dp[i][j][tt]+dp[i-1][j][tt-1])%MOD; 判断边界并计算
                if(i<n-1) dp[i][j][tt]=(dp[i][j][tt]+dp[i+1][j][tt-1])%MOD; 过程中模因为模不会影响结果，不模会爆，只能拿七个点
                if(j>0) dp[i][j][tt]=(dp[i][j][tt]+dp[i][j-1][tt-1])%MOD; 
                if(j<m-1) dp[i][j][tt]=(dp[i][j][tt]+dp[i][j+1][tt-1])%MOD;
            }
        }
    }
    cout<<dp[r2][c2][t]%MOD; 输出
}