洛谷 P1002过河卒 题解

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

但是这题有很多坑：

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

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

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

所以完整代码如下：

#include
using namespace std;
int main()
{
	long long a[21][21];
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	for(int i=0;i<=20;i++)
		for(int k=0;k<=20;k++)
			a[i][k]=1;
	a[x2][y2]=0;
	if(x2>=2 && y2>=1) a[x2-2][y2-1]=0;
	if(x2>=2 && y2>=1) a[x2-1][y2-2]=0;
	a[x2+2][y2+1]=0;
	a[x2+1][y2+2]=0;
	if(x2>=2) a[x2-2][y2+1]=0;
	if(x2>=1) a[x2-1][y2+2]=0;
	if(y2>=1) a[x2+2][y2-1]=0;
	if(y2>=2) a[x2+1][y2-2]=0;
	if(x2==2) 
	for(int k=y2+1;k<=20;k++) a[0][k]=0;
	if(x2==1) 
	for(int k=y2+2;k<=20;k++) a[0][k]=0;
	if(x2==0) 
	for(int k=y2;k<=20;k++) a[0][k]=0;
	if(y2==2) 
	for(int i=x2+1;i<=20;i++) a[i][0]=0;
	if(y2==1) 
	for(int i=x2+2;i<=20;i++) a[i][0]=0;
	if(y2==0) 
	for(int i=x2;i<=20;i++) a[i][0]=0;
	for(int i=1;i<=20;i++)
	{
		for(int k=1;k<=20;k++)
		{
		    if(a[i][k]!=0)
			    a[i][k]=a[i-1][k]+a[i][k-1];
		}
	}
	cout<

因为作者非常糟糕，所以若有不足请在评论区中指出。