P1002 [NOIP2002 普及组] 过河卒 题解

· · 题解

思路分析

我们可以先写八个if判断马所能到达的点（不能越界）
举个例子，若马的位置为（2，2），则它能跳到的点有（1，4）、（3，4）、（4，3）、（0，1）、（1，0）、（4，1）、（0，3）、（3，0）
但其中 （0，1）、（1，0）、（0，3）、（3，0） 是越界不合法的
代码如下所示：

int nh=x-2,nl=y+1;
if(nh>=0&&nl<=m)
  b[nh][nl]=true;
nh=x-1,nl=y+2;
if(nh>=0&&nl<=m)
  b[nh][nl]=true;
nh=x+1,nl=y+2;
if(nh<=n&&nl<=m)
  b[nh][nl]=true;
nh=x+2,nl=y+1;
if(nh<=n&&nl<=m)
  b[nh][nl]=true;
nh=x-2,nl=y-1;
if(nh>=0&&nl>=0)
  b[nh][nl]=true;
nh=x-1,nl=y-2;
if(nh>=0&&nl>=0)
  b[nh][nl]=true;
nh=x+1,nl=y-2;
if(nh<=n&&nl>=0)
  b[nh][nl]=true;
nh=x+2,nl=y-1;
if(nh<=n&&nl>=0)
  b[nh][nl]=true;

当然我们也可以定义dir数组标记方向（这里我用的是上一种方式，比较暴力）

int dir[8][2]={1,2,2,1,1,-2,-2,1,-1,2,2,-1,-1,-2,-2,-1}

做完初始化后，这题就变成了数学递推题
不难看出，某个点是由它的上一个点和左边一个点过来的（过河卒只能往右，下走），所以我们可以得到递推式a[i][j]=a[i-1][j]+a[i][j-1]（要保证b[i][j]==0这个点才可以走），这样就可以解题了。

Code

#include<bits/stdc++.h>
using namespace std;
long long a[101][101],n,m,x,y;
bool b[101][101];
int main()
{
    cin>>n>>m>>x>>y;
    b[x][y]=true;
    int nh=x-2,nl=y+1;//初始化过河卒可以走的点，为0可以走
    if(nh>=0&&nl<=m)
      b[nh][nl]=true;
    nh=x-1,nl=y+2;
    if(nh>=0&&nl<=m)
      b[nh][nl]=true;
    nh=x+1,nl=y+2;
    if(nh<=n&&nl<=m)
      b[nh][nl]=true;
    nh=x+2,nl=y+1;
    if(nh<=n&&nl<=m)
      b[nh][nl]=true;
    nh=x-2,nl=y-1;
    if(nh>=0&&nl>=0)
      b[nh][nl]=true;
    nh=x-1,nl=y-2;
    if(nh>=0&&nl>=0)
      b[nh][nl]=true;
    nh=x+1,nl=y-2;
    if(nh<=n&&nl>=0)
      b[nh][nl]=true;
    nh=x+2,nl=y-1;
    if(nh<=n&&nl>=0)
      b[nh][nl]=true;
    if(!b[0][0])
      a[0][0]=1;//走到a[0][0]有一种情况
    for(int i=1;i<=n;++i)//对a[1..n][0]进行初始化1
    {
        if(!b[i][0]&&a[i-1][0]==1)
          a[i][0]=1;
    }
    for(int i=1;i<=m;++i)
      if(!b[0][i]&&a[0][i-1]==1)
        a[0][i]=1;//对a[0][1..n]进行初始化1
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(b[i][j])
              continue;
            a[i][j]=a[i-1][j]+a[i][j-1];//递推
        }
    }
    cout<<a[n][m];//答案在a[n][m](终点)里
    return 0;
}

管理员求过QAQ