Beyond the Void
BYVoid
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;
}

上次修改时间 2017-02-03

相关日志