这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2151
先开始用的BFS,结果爆栈了,然后换成DP~~~
#include
#include
using namespace std;
int N, P, M, T;
// dp[M][T];
// 表示在M时间上,走到T的方案数
// dp[M][T] = dp[M-1][T-1] + dp[M-1][T+1]
// 初始化dp[0][P] = 1;
int dp[105][105];
int main()
{
while(cin >> N >> P >> M >> T)
{
memset(dp, 0, sizeof(dp));
dp[0][P] = 1;
for(int i=1; i<=M; ++i)
for(int j=1; j<=N; ++j)
{
if(j-1 >= 1)
dp[i][j] += dp[i-1][j-1];
if(j+1 <= N)
dp[i][j] += dp[i-1][j+1];
}
cout << dp[M][T] << endl;
}
}
/*
int cnt;
void BFS(int vis, int time)
{
if(time==M && vis==T)
{
++cnt;
return ;
}
if(vis == T)
return;
if(vis<1 || vis>N)
return;
if(vis >= 2)
BFS(vis-1, time+1);
if(vis <= N-1)
BFS(vis+1, time+1);
}
int main()
{
while(cin >> N >> P >> M >> T)
{
cnt = 0;
BFS(P, 0);
cout << cnt << endl;
}
}
*/