题目
分析
这道题虽然标签是动态规划,但我用的其实是“标数法”。
“标数法”是一种数学方法,至于不清楚的同学可以参见万能的百度。
然后我们可以发现,标数法貌似可以带进这道题里:
每一个点可能的走法是它上面的点的走法数加它右边的点的走法数
即为:
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;
}