Logo CloudLunar

“CodeVS/1010”的版本间的差异

（以“ 分类:棋盘动态规划 ==摘要== {{信息题|过河卒|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|0|数组越界访问}}
+
{{信息题|过河卒|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）和其能够一步走到的地方不允许通过，问方案数。

2014年12月8日 (一) 16:46的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
过河卒 ★☆☆☆☆ 答案正确 100 2014/11/28 18:29:49 数组越界访问（0）

题意

棋盘上，从（0,0）走到（n,m），其中马所在的（n,m）和其能够一步走到的地方不允许通过，问方案数。

题解

阶段性太明显了，很容易得到方程：

显示/移除行号
  1.     f[x][y]=
  2.         f[x-1][y]+f[x][y-1]    //如果(x,y)能走
  3.         0    //如果(x,y)不能走

要特别注意一下，是从(0,0)开始而不是(1,1)，边界问题要特别考虑。

代码

1010.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. int dp[20][20]={},forbed[20][20]={},n,m,x0,y0;
  3. inline void forb(const int &x,const int &y)
  4. {
  5.     if(x<=n&&x>=0&&y<=m&&y>=0)
  6.         forbed[x][y]=1;
  7. }
  8. int main()
  9. {
  10.     scanf("%d%d%d%d",&n,&m,&x0,&y0);
  11.     forb(x0,y0);
  12.     for(int i=-1;i!=3;i+=2)
  13.         for(int j=-1;j!=3;j+=2)
  14.         {
  15.             forb(x0+1*i,y0+2*j);
  16.             forb(x0+2*i,y0+1*j);
  17.         }
  18.     dp[0][0]=1;
  19.     for(int i=0;i<=n;++i)
  20.         for(int j=0;j<=m;++j)
  21.         {
  22.             if(i)//修复数组越界访问2014-11-28 18:29:42
  23.                 dp[i][j]+=dp[i-1][j];
  24.             if(j)
  25.                 dp[i][j]+=dp[i][j-1];
  26.             if(forbed[i][j])
  27.                 dp[i][j]=0;
  28.         }
  29.     printf("%d\n",dp[n][m]);
  30. }
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1010&oldid=797”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]