#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 个位置),卒不能通过这些马控制的点。
输入格式
- 一行包含
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
转移时跳过障碍物即可。