#1861. 过河卒 (Pawn Crossing the River)

过河卒 (Pawn Crossing the River)

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


任务总览

任务名称 时间限制 内存限制 分数
过河卒路径计算 1000 ms 256 MiB 普及组

题目描述

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

image


输入格式

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

输出格式

  • 输出​卒从 AB 能走的路径总数​。

输入输出示例

输入示例 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 ≤ 20dp 计算最多 20 × 20 = 400 次,时间复杂度O(nm),完全可行。

结论

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