题目

链接：https://www.luogu.com.cn/problem/P1002

 解析

这道题适用于了解动态规划的同学。

变量初始化

初始化B点坐标（n, m）和马的坐标（a, b）

初始化方向数组和动态规划数组

long long dp[30][30];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int n, m, a, b;

输入部分

输入n,m,a,b。

 cin >> n >> m >> a >> b;

运算部分

初始化

初始化dp数组。

dp[0][0] = 1;
for (int i = 0; i < 8; i ++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x <= n && y >= 0 && y <= m)dp[x][y] = -1;
}
dp[a][b] = -1;

首先到达自己的点的坐标dp[0][0]肯定只有一种方法，那就是原地不动。

循环方向数组，把那些马可能到的地方给标记一下。

马的地方不能走，设为-1。

推导式

由于卒只能从上面或者左面过来，所以得出

如果遍历到马的话直接设为0，要不然在算的时候直接-1。

dp代码

for (int i = 0; i <= n; i ++)for (int j = 0; j <= m; j ++)if (dp[i][j] == -1)dp[i][j] = 0;else {if (i - 1 >= 0)dp[i][j] += dp[i - 1][j];if (j - 1 >= 0)dp[i][j] += dp[i][j - 1];}

输出

直接输出就可以了。

cout << dp[n][m] << endl;

代码

#include <iostream>
using namespace std;
long long dp[30][30];
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int main() {int n, m, a, b;cin >> n >> m >> a >> b;dp[0][0] = 1;for (int i = 0; i < 8; i ++) {int x = a + dx[i], y = b + dy[i];if (x >= 0 && x <= n && y >= 0 && y <= m)dp[x][y] = -1;}dp[a][b] = -1;for (int i = 0; i <= n; i ++)for (int j = 0; j <= m; j ++)if (dp[i][j] == -1)dp[i][j] = 0;else {if (i - 1 >= 0)dp[i][j] += dp[i - 1][j];if (j - 1 >= 0)dp[i][j] += dp[i][j - 1];}cout << dp[n][m] << endl;return 0;
}