题目

题目传送门

分析

这道题虽然标签是动态规划,但我用的其实是“标数法”。
“标数法”是一种数学方法,至于不清楚的同学可以参见万能的百度


然后我们可以发现,标数法貌似可以带进这道题里:
每一个点可能的走法是它上面的点的走法数加它右边的点的走法数
即为:

a[x][y] = a[x - 1][y] + a[x][y - 1]

因为只有上边和左边的点可以到达当前点。
最后输出目标点就行了。
就这么简单。


接下来分析特殊情况:
马的控制点不可能被走到,所以走法是0。
初始点由于一开始就在那,所以走法是1。
边上的(如最左边的一列)就只能加上面的走法数,因为不可能从左边过来。
接下来只要 快乐 相加就行了

举例

让我们来看一下样例:
目标点在(6,6),马在(3,3)。
看起来就是这样的:(马是!,马的控制点为*)

a 0 0 0 0 0 0
0 0 * 0 * 0 0
0 * 0 0 0 * 0
0 0 0 ! 0 0 0
0 * 0 0 0 * 0
0 0 * 0 * 0 0
0 0 0 0 0 0 b

相应的走法数就应该是:
1 1 1 1 1 1 1
1 2 * 1 * 1 2
1 * 0 1 1 * 2
1 1 1 ! 1 1 3
1 * 1 1 2 * 3
1 1 * 1 * 0 3
1 2 2 3 3 3 6

那么到b点的走法就有六种。

AC代码

#include<iostream>
using namespace std;

struct qp//棋盘单个点的储存
{
	long long sum;
	bool f;//便于识别马的控制点,f=0就不是控制点,f=1就是控制点,这样就可以在后面的遍历中跳过控制点
}a[30][30] = {0};//棋盘最大为20*20

void kz(int x, int y)//空出马的控制点,xy是马的坐标
{
	a[x][y].f = 1;
	a[x - 2][y - 1].f = 1;
	a[x - 1][y - 2].f = 1;
	a[x + 1][y + 2].f = 1;
	a[x + 2][y + 1].f = 1;
	a[x - 1][y + 2].f = 1;
	a[x - 2][y + 1].f = 1;
	a[x + 1][y - 2].f = 1;
	a[x + 2][y - 1].f = 1;
	
	a[x][y].sum = 0;
	a[x - 2][y - 1].sum = 0;
	a[x - 1][y - 2].sum = 0;
	a[x + 1][y + 2].sum = 0;
	a[x + 2][y + 1].sum = 0;
	a[x - 1][y + 2].sum = 0;
	a[x - 2][y + 1].sum = 0;
	a[x + 1][y - 2].sum = 0;
	a[x + 2][y - 1].sum = 0;
}

int main()
{
	int n = 0, m = 0, x = 0, y = 0;
	
	a[2][1].sum = 1;//a[2][2]是a点,这里进行这一步是为了让a点直接继承它上面的1,后面就不用进行特殊判断了
	
	cin >> n >> m >> x >> y;
	
	n+=2;//给棋盘留出边缘,至于空两个是为了防止马跳出棋盘导致RE
	m+=2;
	x+=2;
	y+=2;
	
	kz(x, y);
	
	for(int i = 2; i <= n; i++)//遍历棋盘
	{
		for(int j = 2; j <= m; j++)
		{
			if(a[i][j].f == 0)//如果不是控制点
			{
				a[i][j].sum = a[i - 1][j].sum + a[i][j - 1].sum;//计算走法数
			}
		}
	}
	
	cout << a[n][m].sum;//输出b点
	
	return 0;
}