USACO MAR08 Silver Cow Travelling 遊蕩的奶牛

看到題我想到了過河卒問題,不同的是這道題規定奶牛的移動方向是任意的,但是規定了一個時間,所以可以動態規劃。

狀態

* 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爲目標點列) 
/*
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;
}

相關日誌