🧩 题目大意

在一个 $ (n+1) \times (m+1) $ 的棋盘上，有一个“过河卒”从起点 $ A(0, 0) $ 出发，目标是走到终点 $ B(n, m) $。卒每次只能 向右或向下 移动一格。

但棋盘上还有一个固定的“马”（位于 $(hx,hy)$），它会控制自己所在的位置以及 8 个“日”字跳跃可达的点（即中国象棋中马的走法）。卒 不能经过这些被控制的点。

要求：计算从 A 到 B 的合法路径总数。

⚠️ 注意：马不会移动！只是一次性标记控制区域。

---

📌 解题思路

✅ 1. 路径问题 → 动态规划

由于卒只能向右或向下走，这是一个典型的 二维网格路径计数问题，非常适合用 动态规划（DP） 解决。

设 dp[i][j] 表示从 (0, 0) 走到 (i, j) 的合法路径数。

状态转移方程为：
$$dp[i][j]=\{\begin{array}{ll}0,& \text{如果 }(i,j)\text{ 被马控制}\\ dp[i-1][j]+dp[i][j-1],& \text{否则}\end{array}$$

边界条件：

• dp[0][0] = 1（起点）
• 第一行：只能从左边来 → dp[0][j] = dp[0][j-1]
• 第一列：只能从上面来 → dp[i][0] = dp[i-1][0]

✅ 2. 标记马的控制点

马在 (hx, hy)，其 8 个控制点偏移量为：

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

💡 注意：题目图中马的控制点是标准“日”字，但原代码写反了方向（不过不影响结果，只要覆盖全部8点即可）。

我们将所有控制点（包括马本身）在 blocked[i][j] 数组中标记为 1，表示不可通行。

✅ 3. 数据范围与类型

• $ n, m \leq 20 $，最大路径数约为 $ C_{40}^{20} \approx 1.3 \times 10^{11} $
• 必须使用 long long，否则会溢出！

---

💻 代码详解（附注释）

#include <stdio.h>
#include <string.h>

int main() {
    int n, m, hx, hy;
    scanf("%d %d %d %d", &n, &m, &hx, &hy);

    // 马的8个控制方向（dx, dy）
    int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

    // blocked[i][j] == 1 表示该点被马控制，不可走
    int blocked[25][25];
    memset(blocked, 0, sizeof(blocked));

    // 标记马自身位置
    blocked[hx][hy] = 1;

    // 标记马能跳到的8个点
    for (int i = 0; i < 8; i++) {
        int x = hx + dx[i];
        int y = hy + dy[i];
        if (x >= 0 && x <= n && y >= 0 && y <= m) {
            blocked[x][y] = 1;
        }
    }

    // dp[i][j]：从 (0,0) 到 (i,j) 的路径数
    long long dp[25][25];
    memset(dp, 0, sizeof(dp));

    // 起点是否被控制？
    if (!blocked[0][0]) {
        dp[0][0] = 1;
    }

    // 初始化第一行
    for (int j = 1; j <= m; j++) {
        if (!blocked[0][j]) {
            dp[0][j] = dp[0][j - 1]; // 只能从左边来
        }
    }

    // 初始化第一列
    for (int i = 1; i <= n; i++) {
        if (!blocked[i][0]) {
            dp[i][0] = dp[i - 1][0]; // 只能从上面来
        }
    }

    // 填充其余格子
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!blocked[i][j]) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
            // 否则保持为 0（不可达）
        }
    }

    printf("%lld\n", dp[n][m]);
    return 0;
}

🔍 注意：原题代码中 nx, ny 的顺序虽然和常规不同，但只要覆盖了全部8个方向，结果正确。此处我按标准“日”字修正，更清晰。

---

🧪 样例验证

输入：

6 6 3 3

• 马在 (3,3)，控制点包括 (1,2), (2,1), (2,5), (1,4), (4,5), (5,4), (5,2), (4,1) 等。
• 起点 (0,0) 和终点 (6,6) 未被控制。
• 最终路径数为 6，符合输出。

---

📌 memset函数解释

memset 是 C 语言标准库中的一个内存操作函数，定义在 <string.h> 头文件中。它的作用是：将一块连续的内存区域的每一个字节都设置为指定的值。

🔹 函数原型

#include <string.h>
void *memset(void *s, int c, size_t n);

参数说明：

参数	类型	含义
s	void*	要操作的内存起始地址（通常是数组名或指针）
c	int	要写入的字节值（只取低8位，即0~255）
n	size_t	要设置的字节数

✅ 返回值：返回 s（一般我们不使用返回值）

---

🔸 最常见用法：清零

int arr[100];
memset(arr, 0, sizeof(arr));

• 把 arr 数组的 所有字节 都设为 0
• 结果：每个 int 元素都变成 0

这等价于：

for (int i = 0; i < 100; i++) arr[i] = 0;

但 memset 是底层优化的，通常更快。

---

🌰 实际例子

例1：清零整型数组

#include <stdio.h>
#include <string.h>

int main() {
    int a[5] = {1, 2, 3, 4, 5};
    memset(a, 0, sizeof(a));  // 全部清零
    
    for (int i = 0; i < 5; i++)
        printf("%d ", a[i]);  // 输出：0 0 0 0 0
    
    return 0;
}

例2：初始化字符数组

char str[10];
memset(str, 'A', 5);   // 前5个字节设为 'A'
str[5] = '\0';         // 添加字符串结束符
printf("%s\n");        // 输出：AAAAA

例3：清零二维数组

int dp[10][10];
memset(dp, 0, sizeof(dp));  // 整个10×10数组清零

---

⚠️ 重要注意事项（必读！）

❗ memset 是按字节赋值的！

这意味着：

• ✅ memset(arr, 0, sizeof(arr)) → 所有元素 = 0（安全）
• ✅ memset(arr, -1, sizeof(arr)) → 所有元素 = -1（因为 -1 的补码是全 1）
• ❌ memset(arr, 1, sizeof(arr)) → 不会让每个 int 变成 1！

为什么？

假设 int 占 4 字节：

• memset(arr, 1, sizeof(arr)) 会把每个字节设为 0x01
• 所以一个 int 变成 0x01010101 = 16843009，不是 1！

💡 结论：memset 只安全用于清零（或设为 -1）

---

🔧 在算法题中的典型用途

1. 初始化标记数组

bool visited[1000];
memset(visited, false, sizeof(visited));  // 全设为 false

2. 清空 DP 数组

long long dp[25][25];
memset(dp, 0, sizeof(dp));  // 路径数从0开始

3. 重置计数数组

int count[256];
memset(count, 0, sizeof(count));  // 字符计数归零

---

✅ 正确使用技巧

目标	写法	是否安全
清零	memset(arr, 0, sizeof(arr))	✅ 安全
全设为 -1	memset(arr, -1, sizeof(arr))	✅ 安全
全设为 1	memset(arr, 1, sizeof(arr))	❌ 危险！
全设为 1（正确做法）	用循环：for(...) arr[i]=1;	✅ 安全

---

📝 总结

• memset = memory set（内存设置）
• 作用：按字节批量设置内存
• 最常用：清零数组（memset(arr, 0, sizeof(arr))）
• 警告：不要用它给 int 数组赋非 0/-1 的值
• 包含头文件：#include <string.h>

💡 记住口诀：“memset 只清零，赋值用循环” —— 这样就不会出错了！

⚠️ 常见错误 & 优化建议

错误	说明
用 int 存路径数	必然溢出！必须用 long long
忘记判断起点被控制	若 (0,0) 被马控制，答案应为 0
控制点越界未判断	必须检查 0 <= x <= n 且 0 <= y <= m
方向数组写错	导致漏标控制点，答案偏大

---

✅ 总结

• 核心思想：动态规划 + 障碍标记
• 关键点：正确标记马的控制区域，使用 long long 防溢出
• 时间复杂度：$ O(nm) $，空间 $ O(nm) $，完全满足数据范围

这道题是 动态规划入门的经典模板题，掌握后可轻松应对类似“带障碍的网格路径计数”问题。