洛谷 P1002过河卒 题解

其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边（我们称之为左点）或者上边（我们称之为上点）过来，所以根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和。这就是小学数学中经常使用的标数法，对于马的控制点也完全适用，只要将到达该点的路径数目设置为0即可。

但是这题有很多坑：

1.卒不能把马吃掉，否则这题肯定不止橙题；

2.如果马有控制点在X轴或Y轴上，那么整个X轴或Y轴都要标为0.为什么呢？我们可以举个例子。

如上图，蓝色的是卒（将卒的位置标为(0,0)），红色的则是马的控制点，且不说(1,1)这个位置有一个控制点，就算把这个点去掉，卒还是到不了(0,3)或者(0,5)，因为卒必须得绕开(0,2)和(0,4)上的控制点，这就意味着它离开了X轴，那么它就不可能再回去了（因为只能往右或往下走）

所以完整代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a[21][21];
	int x1,y1,x2,y2;
	cin>>x1>>y1>&