題目

鏈接：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;
}