摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
过河卒 ★☆☆☆☆ 答案正确 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]);
}

著作权声明[编辑]

关于[编辑]