C++过河卒（动态规划）

解题思路:

首先考虑暴力解法，果不其然会超时，然后发现每个点的状态只会由左边一个点和上边一个点转化而来，想到用dp，令dp[x][y]为到该点的路径数量，可知
dp[x][y]=dp[x-1][y]+dp[x][y-1]。

注意事项:

//需要注意初始化第一行（列）时，第一行（列）没有非法点时，第一行（列）全为1

//但当第一行（列）有非法点时，无法达到非法点后续位置，故非法点及之后的点会全为0

前半部分为DFS做法，会超时，可以直接参考后半部分的dp做法。

参考代码:

#include <iostream>
#include <vector>
using namespace std;

/*暴力DFS做法
vector<int> unlow_x, unlow_y;
int res = 0;
int a, b, c, d;

bool find(int x, int y) {
	for (int i = 0; i < unlow_x.size(); i++) {
		if (x == unlow_x[i] && y == unlow_y[i])
			return true;
	}
	return false;
}
void dfs(int x, int y) {
	if (x == a && y == b) {
		res++;
		return;
	}
	if (find(x,y)||x>a||y>b)
		return;
	dfs(x + 1, y);
	dfs(x, y + 1);
}

int main()
{
	cin >> a >> b >> c >> d;
	unlow_x.push_back(c + 1);
	unlow_y.push_back(d + 2);
	unlow_x.push_back(c + 1);
	unlow_y.push_back(d - 2);
	unlow_x.push_back(c - 1);
	unlow_y.push_back(d + 2);
	unlow_x.push_back(c - 1);
	unlow_y.push_back(d - 2);
	unlow_x.push_back(c + 2);
	unlow_y.push_back(d + 1);
	unlow_x.push_back(c + 2);
	unlow_y.push_back(d - 1);
	unlow_x.push_back(c - 2);
	unlow_y.push_back(d + 1);
	unlow_x.push_back(c - 2);
	unlow_y.push_back(d - 1);
	unlow_x.push_back(c);
	unlow_y.push_back(d);
	dfs(0, 0);
	cout << res;
	return 0;
}*/

/*DP做法*/
//(a,b)为终点坐标，（c,d）为马坐标，fx,fy存储非法点相对马的dx和dy
int a, b, c, d;
vector<int> fx{ 0,1,1,2,2,-1,-1,-2,-2 }, fy{ 0,2,-2,1,-1,2,-2,1,-1 };

/*判断是否为合法点，如果该点是非法点，返回false*/
bool judge(int x, int y) {
	for (int i = 0; i < fx.size(); i++) {
		if (x == c + fx[i] && y == d + fy[i])
			return false;
	}
	return true;
}

int main() {
	cin >> a >> b >> c >> d;
	//初始化dp表，dp[x][y]表示到（x,y)点的路径数量
	//需要注意当第一行（列）没有非法点时，第一行（列）全为1
	//但当其有非法点时，无法达到非法点后续位置，故非法点及之后的点会全为0
	vector<vector<long long>> dp(a + 1, vector<long long>(b + 1, 0));
	
	//初始化第一行
	for (int i = 0; i <= b; i++) {
		if (judge(0, i))
			dp[0][i] = 1;
		else break;
	}
	//初始化第一列
	for (int j = 0; j <= a; j++) {
		if (judge(j, 0))
			dp[j][0] = 1;
		else break;
	}

	//开始动态规划，dp[x][y]=dp[x-1][y]+dp[x][y-1]
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			if (judge(i, j)) {
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	cout << dp[a][b];
	return 0;
}