过河卒

过河卒

分析：

由题目可知每一步我们只能向下或者向右进行移动，故对任意一个可以非控制点，我们都有两种方式到达：

1. 由其上方的点向下移动；
2. 由其左边的点向右移动。

所以到任意点的方式为 $\mathrm{到}\mathrm{点}\mathrm{（}x\mathrm{，}y\mathrm{）}\mathrm{的}\mathrm{方}\mathrm{式}=\mathrm{到}\mathrm{点}\mathrm{（}x-1\mathrm{，}y\mathrm{）}\mathrm{的}\mathrm{方}\mathrm{式}+\mathrm{到}\mathrm{点}\mathrm{（}x\mathrm{，}y-1\mathrm{）}\mathrm{的}\mathrm{方}\mathrm{式}到点（x，y）的方式=到点（x-1，y）的方式+到点（x，y-1）的方式$。

而对于控制点而言，我们可以用一个二维数组记录哪些点是控制点，而后将每一个扫描到的控制点$\mathrm{（}x\mathrm{，}y\mathrm{）}（x，y）$的到达方式数设为0，这样经过控制点$\mathrm{（}x\mathrm{，}y\mathrm{）}（x，y）$的路径无法从控制点获得任何方式数。

对于边界问题，可以发现马的控制点最多向外到达2格，所以可以将整个棋盘以 $\mathrm{（}2\mathrm{，}2\mathrm{）}（2，2）$ 为原点 ,再将棋盘外的点全当作控制点处理，就可以很好的处理边界。

AC代码：

#include<iostream>
using namespace std;
const int N=20+3;

long long borad[N][N];  //记录每个点的到达方式，注意数据范围

int access[N][N];  //记录控制点

int main(){
    int x,y;
    cin>>x>>y;
    for(int i=1;i<=x+2;++i)
    {
        access[i][1]=1;
    }
    for(int i=1;i<=y+2;++i)
    {
        access[1][i]=1;
    }
    int hx,hy;
    cin>>hx>>hy;
    hx=hx+2;
    hy=hy+2;
    access[hx][hy]=1;
    access[hx-2][hy+1]=1;
    access[hx-2][hy-1]=1;
    access[hx-1][hy+2]=1;
    access[hx-1][hy-2]=1;
    access[hx+1][hy+2]=1;
    access[hx+1][hy-2]=1;
    access[hx+2][hy+1]=1;
    access[hx+2][hy-1]=1;
  
    borad[2][2]=1;
    for(int i=2;i<=x+2;++i)
    {
        for(int j=2;j<=y+2;++j){
            if(i==j&&i==2) continue;
            borad[i][j]=borad[i-1][j]+borad[i][j-1];
            if(access[i][j]) borad[i][j]=0;
            
        }
    }
    
    
    cout<<borad[x+2][y+2];
    return 0;
}