问题：过河卒 (Pawn Crossing the River)

任务总览

题目描述

在 n × m 的棋盘上，有一个过河卒 (pawn) 需要从起点 A(0,0) 走到终点 B(n,m)。卒只能 向右或向下 移动。棋盘上有一匹对方的马 (knight) 位于 C(x,y)，马能够控制 ​9 个位置​（自己的位置和它能够跳到的 8 个位置），卒不能通过这些​马控制的点​。

输入格式

• 一行包含 4 个整数：
  • n m x y —— 目标点 B(n,m) 以及马的位置 C(x,y)。

输出格式

• 输出​卒从 A 到 B 能走的路径总数​。

输入输出示例

输入示例 1

6 6 3 2

输出示例 1

17

题目分析

1. 问题拆解

• 这是一个带有障碍物的经典路径计数问题，可用 动态规划 解决。
• 由于 n,m ≤ 20，搜索空间小，可以使用 dp 数组存储到达每个格子的路径数。

2. 影响因素​

• ​普通路径计数​：
  • 只有向下或者向右的走法，典型的​动态规划 (DP) 计数问题​。
  • 不考虑马的阻挡时，路径数量满足： dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i-1][j] + dp[i][j-1]
• ​马的影响​：
  • 需要标记​马及其控制区域​，避免计算经过这些点的路径。

时间复杂度分析

• 由于 n, m ≤ 20，dp 计算最多 20 × 20 = 400 次，时间复杂度 仅 O(nm)，完全可行。

结论

此问题是​带障碍物的动态规划路径计数问题​，主要难点是正确​标记马的控制点​，然后在 dp 转移时跳过障碍物即可。