马拦过河卒-题解（C++代码）(含思路)

解题思路:

    用dp思路逆推，观察终点到终点的路线一定由上一个点和左边个点而来，故该点的路径数就是上面那个点和左边那个点的路径数和,使用一个二维数组dp[i][j]来存储起点到( i , j )点的路径数，前面这个推论就可以表达成:dp[i][j] = dp[i-1][j] + dp[i][j-1]

然后在这之中还要考虑马拦截的坐标，继续按上面那个思路，假设现在有一个点上方是拦截点，左边是正常的，那么到这个点的方法就只能是从左边而来，即

dp[i][j] = dp[i][j-1],但我们只要将所有dp[i][j]初始化为0，依然可以用dp[i][j] = dp[i-1][j] + dp[i][j-1]，即将拦截点的路径数计为0。

注意事项:

题目中说的是棋盘，且含有0，0，故此题中for遍历需要遍历到n,m，因为棋盘其实就可以看作是一个二维数组，而输入的数据就直接是二维数组的下标，不需要再进行减一操作

还有就是注意边界

参考代码:

#include<iostream>
using namespace std;
int n, m;
long dp[30][30];//将说有点初始化为0
int map[30][30];
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { -1,-2,-2,-1,1,2,2,1 };
void Set(int x, int y)//初始化马拦截点
{
	map[x][y] = 1;
	for (int i = 0; i < 8; ++i)
		if (x + dx[i] >= 0 && y + dy[i] >= 0 && x + dx[i] <= n && y + dy[i] <= m)
			map[x + dx[i]][y + dy[i]] = 1;
}
int main()
{
	int horsex, horsey;
	cin >> n >> m >> horsex >> horsey;
	Set(horsex, horsey);
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j <= m; ++j)
		{
			if (map[i][j] == 1)//只有该点是正常点才进行路径计算
				continue;
			if (i == 0 && j == 0)//起点初始化，到起点的路径为1
				dp[i][j] = 1;
			else if (i == 0 && j != 0)//第一行单独列出计算
				dp[i][j] = dp[i][j - 1];
			else if (i != 0 && j == 0)//第一列单独列出计算
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//递推公式
		}
	}
	cout << dp[n][m];
	return 0;
}