文字教学

这道题是经典的动态规划+路径计数问题，核心思路是利用卒只能向右/向下走的规则，结合马的控制点限制来递推路径数：

1. 标记控制点：先标记马的位置和它跳“日”字能到达的8个位置，这些位置卒无法经过，路径数为0。
2. 动态规划状态：用 dp[i][j] 表示从起点 (0,0) 走到 (i,j) 的路径数。
3. 状态转移：
   • 若 (i,j) 是控制点，dp[i][j] = 0；
   • 否则，dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方或左方走来）。
4. 初始化：起点 dp[0][0] = 1；第一行只能从左边来，第一列只能从上方来，若未被控制则路径数等于前一个位置的路径数。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 25;
ll dp[N][N];
bool vis[N][N];
// 马的8个跳跃方向
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

int main() {
    int n, m, hx, hy;
    cin >> n >> m >> hx >> hy;
    // 标记马的位置和控制点
    vis[hx][hy] = true;
    for (int i = 0; i < 8; ++i) {
        int nx = hx + dx[i], ny = hy + dy[i];
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {
            vis[nx][ny] = true;
        }
    }
    // 初始化起点
    dp[0][0] = vis[0][0] ? 0 : 1;
    // 处理第一行
    for (int j = 1; j <= m; ++j) {
        dp[0][j] = vis[0][j] ? 0 : dp[0][j-1];
    }
    // 处理第一列
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = vis[i][0] ? 0 : dp[i-1][0];
    }
    // 动态规划递推
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = vis[i][j] ? 0 : dp[i-1][j] + dp[i][j-1];
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}