题目描述

AA 点有一个过河卒，需要走到目标 BB 点。

卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图的 CC 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。

例如：下图 CC 点可以控制 99 个点（图中的 P1,P2 \dots P8P1,P2…P8 和 CC ），卒不能通过对方马的控制点。 棋盘用坐标表示，现给定 AA 点位置为 (0,0)(0,0)， BB 点位置为 (n,m)(n,m) (n,mn,m 为不超过 1010 的整数)，马的位置 CC 为 (X,Y)(X,Y)（约定: CC 点与 AA 点不重叠，与 BB 点也不重叠）。

要求你计算出卒从 AA 点能够到达 BB 点的路径的条数。

输入

BB 点的坐标 (n,m)(n,m) 以及对方马的坐标 (X,Y)(X,Y)；（马的坐标一定在棋盘范围内，但要注意，可能落在边界的轴上）

输出

输出卒从 AA 点能够到达 BB 点的路径条数。

样例

输入

6 6 3 2

输出

17

来源

递推

#include<bits/stdc++.h>
using namespace std;
int a[25][25];
int main(){
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    for(int i=0;i<=n;i++)for(int j = 0;j<=m;j++)a[i][j] = -1;
    int dx[10]={0,-1,-1,-2,-2,1,1,2,2};
    int dy[10]={0,-2,2,-1,1,-2,2,-1,1};
    for(int i=0;i<=9;i++){
        int ix=dx[i]+x,iy=dy[i]+y;
        if(ix>=0&&ix<=n&&iy>=0&&iy<=m)a[ix][iy] = 0;
    }
    a[0][0]=1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(i==0&&a[i][j]==-1)a[i][j]=a[i][j-1];
            else if(j==0&&a[i][j]==-1)a[i][j]=a[i-1][j];
            else if(a[i][j]==-1)a[i][j]=a[i][j-1]+a[i-1][j];
        }
    }
    cout<<a[n][m];
    return 0;
}