九 28
看到题我想到了过河卒问题，不同的是这道题规定奶牛的移动方向是任意的，但是规定了一个时间，所以可以动态规划。
状态
* F[i,j,t] 表示从起始点经过t时间走到点(i,j)的路径条数
状态转移方程
* F[i,j,t]=F[i-1,j,t-1] + F[i+1,j,t-1] + F[i,j-1,t-1] + F[i,j+1,t-1]
边界条件
* F[i],j,0]=0 (1<=i<=N,1<=j<=M)
* F[Sx,Sy,0]=1 (Sx为起始点行,Sy为起始点列)
目标结果
* F[Tx,Ty,T] (Tx为目标点行,Ty为目标点列)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | /* ID: cmykrgb1 PROG: ctravel LANG: C++ */ #include <iostream> #define MAX 101 using namespace std; int N,M,T,Sx,Sy,Tx,Ty,ans; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; bool Map[MAX][MAX]; int F[MAX][MAX][20]; void init() { int i,j,k; char c; freopen("ctravel.in","r",stdin); freopen("ctravel.out","w",stdout); cin >> N >> M >> T; for (i=1;i<=N;i++) { for (j=1;j<=M;j++) { cin >> c; if (c=='*') Map[i][j]=true; for (k=1;k<=T;k++) F[i][j][k]=-1; F[i][j][0]=0; } } cin >> Sx >> Sy >> Tx >> Ty; F[Sx][Sy][0]=1; } int dp(int x,int y,int t) { int i,px,py,V=0; for (i=0;i<4;i++) { px=x+dx[i]; py=y+dy[i]; if (px>=0 && px<=N && py>=0 && py<=M && !Map[px][py]) { if (F[px][py][t-1]==-1) F[px][py][t-1]=dp(px,py,t-1); V+=F[px][py][t-1]; } } return V; } int main() { init(); ans=dp(Tx,Ty,T); cout << ans << endl; return 0; } |
Recent Comments