给定一个 \(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
来源: http://www.bubuko.com/infodetail-3460627.html