（以“ 分类:棋盘动态规划 ==摘要== {{信息题|过河卒|http://www.codevs.cn/problem/1010/|1|100|time=2014/11/28 18:29:49|0|数组越界访问}} ==题意== ...”为内容创建页面） |
小 （格式） |
||
| 第2行： | 第2行： | ||
[[分类:棋盘动态规划]] | [[分类:棋盘动态规划]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|过河卒|http://www.codevs.cn/problem/1010/|1|100|time=2014/11/28 18:29:49 | + | {{信息题|过河卒|http://www.codevs.cn/problem/1010/|1|100|time=2014/11/28 18:29:49|数组越界访问|0}} |
==题意== | ==题意== | ||
棋盘上，从（0,0）走到（n,m），其中马所在的（n,m）和其能够一步走到的地方不允许通过，问方案数。 | 棋盘上，从（0,0）走到（n,m），其中马所在的（n,m）和其能够一步走到的地方不允许通过，问方案数。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 过河卒 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/28 18:29:49 | 数组越界访问（0） |
棋盘上，从（0,0）走到（n,m），其中马所在的（n,m）和其能够一步走到的地方不允许通过，问方案数。
阶段性太明显了，很容易得到方程：
CloudLunar
f[x][y]=
f[x-1][y]+f[x][y-1] //如果(x,y)能走
0 //如果(x,y)不能走
要特别注意一下，是从(0,0)开始而不是(1,1)，边界问题要特别考虑。
| 1010.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
int dp[20][20]={},forbed[20][20]={},n,m,x0,y0;
inline void forb(const int &x,const int &y)
{
if(x<=n&&x>=0&&y<=m&&y>=0)
forbed[x][y]=1;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&x0,&y0);
forb(x0,y0);
for(int i=-1;i!=3;i+=2)
for(int j=-1;j!=3;j+=2)
{
forb(x0+1*i,y0+2*j);
forb(x0+2*i,y0+1*j);
}
dp[0][0]=1;
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)
{
if(i)//修复数组越界访问2014-11-28 18:29:42
dp[i][j]+=dp[i-1][j];
if(j)
dp[i][j]+=dp[i][j-1];
if(forbed[i][j])
dp[i][j]=0;
}
printf("%d\n",dp[n][m]);
}
|