题目内容

P1002

大意:一过河卒,在(0,0)处,在某处有一个马,马所在点以及马一步能到的点过河卒不能走,过河卒只能向右或向下走,求到目标点B的方案数

解题思路

分析:当过河卒到一个点(x,y)时,他要么是从(x-1,y)来的,要么是从(x,y-1)来的,令f(x,y)为过河卒到达(x,y)的方案数,根据加法原理,有以下转移方程式:

\begin{cases}
f(mx,my)=0\quad(mx,my)\text{为马的位置及马的控制点}\
f(i,j)=f(i-1,j)+f(i,j-1)
\end{cases}

记得特判马的控制点及马本身的位置。

代码细节

妈的这道橙题居然卡了我好久,有一些代码实现上的细节:

  • 注意数组越界,为解决这个问题可以一次性将所有点的横纵坐标都+1
  • 注意f(1,0)要设初始值1,不然推出来的所有结果都是0
  • 由于最终结果可能很大,所以f(x,y)数组要开long long
  • 注意题目给出的坐标先是B点的,然后是马的坐标

具体实现:

#include <cstdio>
typedef unsigned long long ull;
ull f[30][30];//f数组
bool mk[30][30];//mk记录某点是否被马控制(不能走)
int hx,hy,bx,by;
const int fx[8]={1,1,2,2,-1,-1,-2,-2};
const int fy[8]={2,-2,1,-1,2,-2,1,-1};

bool chk(int x,int y)//检查点是否越界用
{
    return x>=1&&y>=1;
}

int main()
{
    scanf("%d %d %d %d",&bx,&by,&hx,&hy);
    bx++,by++,hx++,hy++;//一次性都加一
    for(int k=0;k<8;k++)//枚举马的八种控制点方案
    {
        int xx=hx+fx[k],yy=hy+fy[k];
        if(chk(xx,yy))
            mk[xx][yy]=1;
    }
    mk[hx][hy]=1;//不要忘记马本身也要标记
    f[1][0]=1;
    for(int i=1;i<=27;i++)
        for(int j=1;j<=27;j++)
        {
            if(mk[i][j])//如果不能走就直接过
                continue;
            f[i][j]=f[i-1][j]+f[i][j-1];
        }
    printf("%llu\n",f[bx][by]);//输出记得llu
    return 0;
}
最后修改日期:2020年2月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。