CodeVS/1010

摘要

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

题意

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

题解

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

显示/移除行号

    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]); }