c++过河卒（递推求解）题解

大家好，我是屁孩君，今天屁孩君拿出一道十分典型的递推题跟大家分享。
先让我们来康康题目吧！
A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如下图 C 点可以控制 9 个点（图中的P1，P2 … P8 和 C）。卒不能通过对方马的控制点。 棋盘用坐标表示，现给定A 点位置为（0,0）B 点位置为（n,m）(n,m 为不超过 10 的整数)，马的位置为C（X,Y）（约定: C点与A点不重叠，与B点也不重叠）。要求你计算出卒从 A 点能够到达 B 点的路径的条数。

输入
B点的坐标（n,m）以及对方马的坐标（X,Y）（马的坐标一定在棋盘范围内，但要注意，可能落在边界的轴上）

输出
样例
输入
6 6 3 2
输出
17
注意：每个点的路径条数代表的是到达此点有几种方法。

不包含马和马的控制点路径条数规律是什么？

正常情况下，也就是元素不在第一列，第一行，这种情况下，a[i][j]的路径条数等于a[i-1]+a[i][j-1]（a[i][j]的正上方与左边的元素之和）。
因为卒只能向右或向下走，所以a[i][j]的路径条数等于a[i-1]+a[i][j-1]（a[i][j]的正上方与左边的元素之和）

但是，还有一种情况，a[i][j]的位置在第一列或第一行，这样一来，a[i][j]的正上方或a[i][j]的左边的元素不就没了吗？所以我们要加两个判断语句，切记，要分清情况，判断是否是第一行或第一列，如果是在第一列，那我们就只加上他的正上方的元素，如果是在第一行，那我们就只加上左边的元素。


现在，还有一种情况，那就是，此元素位于第一行第一列，那我们就在设一个判断语句就ok了，这样就是没有马和马的控制点的路径条数的规律了！

包含马和马的控制点的路径条数如何求解？

那如果我们又加上马和马的控制点呢，这其实也很简单，我们只要把马和马的控制点给设置为零，那我们就算把他加上也无碍。但是把马的位置上的元素设为零是挺简单的，但是，你把马的控制点也设为零，就十分麻烦，并且容易打错，不过，这一步只要仔细一点就行了！

算法

讲了这么多，我们又来到了熟悉的算法区。
1：将我们定义的二维数组全部初值设为1。
2：将马的位置于马的控制点的位置的元素设为0。
3：双重循环遍历出每个点的路径条数（不包括马和马的控制点，第一行第一列的元素，如果遇到，直接continue）。
4：输出目标点的路径条数。

分步完成

1：将我们定义的二维数组全部初值设为1。

for(int i=0;i<=n;i++)
{
	for(int j=0;j<=m;j++)a[i][j]=1;
}
1
2
3
4

2：将马的位置于马的控制点的位置的元素设为0。

a[x][y]=0;
if(x-1>=0&&y-2>=0)a[x-1][y-2]=0;
if(x-2>=0&&y-1>=0)a[x-2][y-1]=0;
if(x-2>=0&&y+1<=m)a[x-2][y+1]=0;
if(x-1>=0&&y+2<=m)a[x-1][y+2]=0;
if(x+1<=n&&y+2<=m)a[x+1][y+2]=0;
if(x+2<=n&&y+1<=m)a[x+2][y+1]=0; 
if(x+2<=n&&y-1>=0)a[x+2][y-1]=0;
if(x+1<=n&&y-2>=0)a[x+1][y-2]=0;
1
2
3
4
5
6
7
8
9

3：双重循环遍历出每个点的路径条数（不包括马和马的控制点，第一行第一列的元素，如果遇到，直接continue）。

for(int i=0;i<=n;i++)
{
	for(int j=0;j<=m;j++)
	{
		if(i==0&&i==j)continue; 
		if(a[i][j]==0)continue;
		if(i==0)
			a[i][j]=a[i][j-1];
		if(j==0)a[i][j]=a[i-1][j];
		if(i!=0&&j!=0&&a[i][j]!=0)//正常情况
			a[i][j]=a[i-1][j]+a[i][j-1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4:

cout<<a[n][m]<<endl;
1

话不多说，直接上完整代码

#include
using namespace std;
int a[50][50];
int main()
{
	int n,m,x,y,i,j;
	cin>>n>>m>>x>>y;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)a[i][j]=1;
	}
	a[x][y]=0;
	if(x-1>=0&&y-2>=0)a[x-1][y-2]=0;//将马的控制点设为0
	if(x-2>=0&&y-1>=0)a[x-2][y-1]=0;//将马的控制点设为0
	if(x-2>=0&&y+1<=m)a[x-2][y+1]=0;//将马的控制点设为0
	if(x-1>=0&&y+2<=m)a[x-1][y+2]=0;//将马的控制点设为0
	if(x+1<=n&&y+2<=m)a[x+1][y+2]=0;//将马的控制点设为0
	if(x+2<=n&&y+1<=m)a[x+2][y+1]=0;//将马的控制点设为0
	if(x+2<=n&&y-1>=0)a[x+2][y-1]=0;//将马的控制点设为0
	if(x+1<=n&&y-2>=0)a[x+1][y-2]=0;//将马的控制点设为0
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			if(i==0&&i==j)continue; 
			if(a[i][j]==0)continue;//跳过
			if(i==0)
				a[i][j]=a[i][j-1];
			if(j==0)a[i][j]=a[i-1][j];
			if(i!=0&&j!=0&&a[i][j]!=0)
				a[i][j]=a[i-1][j]+a[i][j-1];
		}
	}
	cout<<a[n][m]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

今天就给大家分享到这了！
古德拜！！！
记得一键三连哦！！！