描述

棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

格式

输入格式

一行四个数据，分别表示B点坐标和马的坐标。

输出格式

一个数据，表示所有的路径条数。

样例1

样例输入1

 

6 6 3 3

样例输出1

 

6

限制

每个测试点1s

分析：DP

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 int bx,by; 9 int mx,my;10 int f[30][30];//f[i][j]表示到达 (i,j) 点的移动方案 f[i][j]=sigma f[i][j+1] f[i-1][j] 11 bool can[30][30];12 int a[30]={ 0,-1,1};13 int b[30]={ 0,-2,2};14 int main(){15 16 scanf("%d%d%d%d",&bx,&by,&mx,&my);17 f[0][0]=1;18 can[mx][my]=true;19 can[0][0]=true;20 21 for(int i=1;i<=2;i++)22 for(int j=1;j<=2;j++)23 can[mx+a[i]][my+b[j]]=true,can[mx+b[j]][my+a[i]]=true;24 25 /*26 can[mx-2][my-1]=can[mx-2][my+1]=can[mx+2][my-1]=can[mx+2][my+1]=true;27 can[mx-1][my-2]=can[mx-1][my+2]=can[mx+1][my-2]=can[mx+1][my+2]=true;28 */ 29 for(int i=0;i<=bx;i++){30 for(int j=0;j<=by;j++){31 if(can[i][j]!=true){32 if((can[i-1][j]!=true||(i-1==0&&j==0))&&i-1>=0&&j>=0)33 f[i][j]+=f[i-1][j];34 if((can[i][j-1]!=true||(i==0&&j-1==0))&&i>=0&&j-1>=0)35 f[i][j]+=f[i][j-1];36 }37 }38 }39 cout<