解题报告 P1002 过河卒 【NOIP2002PJ】

题目内容

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