题目描述
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过20的整数)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入输出格式
输入格式：
一行四个数据，分别表示B点坐标和马的坐标。
输出格式：
一个数据，表示所有的路径条数。
输入输出样例
输入样例#1：
6 6 3 3
输出样例#1：
6
解题思路
这题可以自己在草稿纸上数一下，到一个点到底有几种方法，然后思考一下(雾)，即可得到：到达(x,y)的方法数等于到达(x-1,y)的方法数+到达(x,y-1)的方法数，因为到达一个点只能从上或从左，到这个点的方法数自然等于到上的方法数加到左的方法数。然后不能去的地方特判一下，设成0，还有最左边一列和最上边一行递推边界特殊处理一下（见下），然后……就没有然后了。
（粘一个烂大街但又很好懂的解析）对本题稍加分析就能发现，到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点）。根据加法原理，到达某一点的路径条数，就等于到达其相邻的上点或左点的路径数目总和。因此我们可以使用逐列（逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。
假设用F[I,J]到达点（I,J）的路径数目用G[I,J]表示点(I,J)是否为对方马的控制点，G[I,J]=0表示不是对放马的控制点，G[I,J]=1表示是对方马的控制点。则，我们可以得到如下的递推关系式：
F[I,J]=0{G[I,J]=1}
F[I,0]=F[I-1,0]{I>0,G[I,0]=0}
F[0,J]=F[0,J-1]{J>0,G[0,J]=0}
F[I,J]=F[I-1,J]+F[I,J-1]{I>0,J>0,G[I,J]=0}
F[I,0]=F[I-1,0]{I>0,G[I,0]=0}
F[0,J]=F[0,J-1]{J>0,G[0,J]=0}
F[I,J]=F[I-1,J]+F[I,J-1]{I>0,J>0,G[I,J]=0}
上述递推式边界是：F[0,0]:=1。考虑到最大情况下：n=20，m=20，路径条数可能会出现超出长整型范围，所以要用int64或comp类型计数或者高精度运算（是不是要开一个三维数组呢）。
#include<stdio.h> short g[25][25]; int main() { long long bn,bm,n,m; long long f[25][25]; scanf("%lld%lld%lld%lld",&bn,&bm,&n,&m); for(int i=0;i<25;i++) for(int j=0;j<25;j++) g[i][j]=f[i][j]=0; f[0][0]=g[n][m]=1; if(n>=1&&m>=2) g[n-1][m-2]=1; if(n>=2&&m>=1) g[n-2][m-1]=1; if(n>=1) g[n-1][m+2]=1; if(n>=2) g[n-2][m+1]=1; if(m>=2) g[n+1][m-2]=1; if(m>=1) g[n+2][m-1]=1;//这一排if是针对数组越界的，还可以把整个棋盘全体下移再右移两格 g[n+1][m+2]=1; g[n+2][m+1]=1; for(int i=1;i<25;i++) { if(!g[i][0])f[i][0]=f[i-1][0]; if(!g[0][i])f[0][i]=f[0][i-1]; }//边界如果为零，那它后面的都不可到达，我傻傻的把后面的照样赋值为1,0~60分不等 for(int i=1;i<=bn;i++) { //printf("%6lld (%d %d) ",f[i][0],i,0); for(int j=1;j<=bm;j++) { if(g[i][j]) f[i][j]=0; else f[i][j]=f[i-1][j]+f[i][j-1]; //printf("%6lld (%d %d) ",f[i][j],i,j); } //printf(" "); } printf("%lld",f[bn][bm]); return 0; }