[NOIP2002 普及组] 过河卒
时间: 2025-02-05 15:05:29 浏览: 54
### NOIP2002 普及组 过河卒 问题解题思路算法分析
#### 一、题目背景理解
该题目描述了一个棋盘上的过河卒游戏,其中涉及到一个固定的障碍物——马。目标是在避开马的情况下,计算出从起点到终点的所有可能路径数量。
为了简化处理逻辑,在实际编程求解过程中可以将给定坐标的原点由 (0,0) 移动至 (1,1),从而使得边界条件更容易管理[^3]。
#### 二、动态规划方法解析
采用二维数组 `dp[i][j]` 来表示到达位置 `(i,j)` 的不同路线总数:
- 如果当前位置被马占据,则设其值为 0;
- 对于其他未受阻碍的位置,可以从上方或左方两个方向之一移动过来,因此有如下状态转移方程:
```cpp
if (!isBlocked(i, j)) { // 判断是否被阻挡
dp[i][j] = ((i>0)?dp[i-1][j]:0) + ((j>0)?dp[i][j-1]:0);
}
```
初始化时需设定起始格子即 `(1,1)` 处的路径数目为 1 (`dp[1][1]=1`) ,因为这是唯一确定的一条路;而对于那些位于棋盘边缘外侧以及被马挡住的地方则应设置成不可达的状态(通常赋值为 0)。最终所求的结果就是右下角顶点处存储的数据 `dp[m][n]` (m,n 表示目的地坐标)。
此方法通过自底向上的方式逐步构建解决方案,有效地避免了重复计算,并且时间复杂度仅为 O(m*n),空间上也只需要常量级别的额外开销来保存中间结果。
#### 三、代码实现示意
下面给出一段基于上述思想编写的 C++ 实现片段作为参考:
```cpp
#include <iostream>
using namespace std;
const int MAXN = 25;
int dp[MAXN][MAXN];
bool blocked[MAXN][MAXN];
// 初始化函数...
void init() {
fill(&blocked[0][0], &blocked[MAXN-1][MAXN], false); // 假设默认不阻塞
}
// 设置某些特定位置为阻塞区域...
void setBlock(int x, int y){
blocked[x][y] = true;
}
// 动态规划核心过程...
long long countPaths(int m, int n) {
for (int i=1; i<=m; ++i)
for (int j=1; j<=n; ++j)
if(!blocked[i][j])
dp[i][j]=(i==1&&j==1?1:(dp[i-1][j]+dp[i][j-1]));
return dp[m][n];
}
int main(){
init();
// ...读入数据并调用相应接口...
cout << "Total paths: " << countPaths(endX,endY)<< endl;
return 0;
}
```
阅读全文
相关推荐

















