洛谷 P1002 过河卒

洛谷 P1002 过河卒

思路

菜鸡小学生(loceaner)现在才知道过河卒怎么做……

首先我们把马的控制点全部标记一下（顺便判断一下边界，后面就不用判了）

然后用(DP)来做，需要注意的是如果(f[0][0])也是马的控制点的话，就没法到达(B)点了，所以((0,0))不是控制点才可以到达，且到达此点的方式只有一种，在代码中便是这一句if(!f[0][0]) dp[0][0] = 1;

之后便是(DP)过程了，循环过程中，如果当前点是马的控制点，则直接跳过，如果不是，只要(i)大于(0)，便可以由(dp[i-1][j])转化过来，只要(j)大于(0)，就可以从(dp[i][j - 1])转化过来，总体转移方程为

[egin{equation} dp[i][j] = dp[i][j] + egin{cases} dp[i - 1][j] (i > 0)\ dp[i][j-1](j >0)\ end{cases} end{equation} ]

最后的答案显然在(dp[bx][by])中

代码

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

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

int mx, my, bx, by;
long long dp[21][21];
bool f[21][21];

void pre(int i, int j) {
	if(i >= 0 && i <= bx && j >= 0 && j <= by)
		f[i][j] = true;
	return;
}

int main() {
	bx = read(), by = read(), mx = read(), my  = read();
	pre(mx, my);
	pre(mx - 2, my + 1);
	pre(mx - 2, my - 1);
	pre(mx - 1, my + 2);
	pre(mx - 1, my - 2);
	pre(mx + 1, my + 2);
	pre(mx + 1, my - 2);
	pre(mx + 2, my - 1);
	pre(mx + 2, my + 1);
	if(!f[0][0])dp[0][0] = 1;
	for(int i = 0; i <= bx; i++) {
		for(int j = 0; j <= by; j++) {
			if(f[i][j]) continue;
			if(i > 0) dp[i][j] += dp[i - 1][j];
			if(j > 0) dp[i][j] += dp[i][j - 1];
		}
	}
	cout << dp[bx][by] << '
';
	return 0;
}