NOIP2002普及组过河卒题解：动态规划解法与代码详解

一、题目解读

“过河卒”是2002年NOIP普及组的经典题目（洛谷P1002），要求计算棋盘上卒从A点(0,0)到达B点(n,m)的路径条数。卒仅能向右或向下移动，但需避开马的控制点（马的位置及跳跃一步可达的点）。题目限制n、m≤20，需高效算法求解。

二、解题思路

采用动态规划（DP）。定义状态dp[i][j]为到达(i,j)点的合法路径数。核心思想是路径数由上方和左方转移而来，即dp[i][j] = dp[i-1][j] + dp[i][j-1]。需先标记马的控制点，避免路径经过禁区。

三、解题步骤

1. 输入与初始化：读入n、m及马的位置，创建dp和blocked数组标记控制点。

2. 标记控制点：通过方向数组dx,dy遍历马跳跃的8个方向，标记所有控制点。

3. 边界处理：初始化起点dp[0][0]=1，处理第一列/行路径（若不被控制，则路径数为上方/左方的累加）。

4. 动态规划循环：遍历(i,j)，若(i,j)未被控制，则更新dp[i][j]为上方和左方路径之和。

5. 输出结果：dp[n][m]即终点路径数。

四、代码与注释

#include <iostream>  
#include <vector>  
using namespace std;  

// 马的控制点方向  
const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};  
const int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};  

int main() {  
    int n, m, horse_x, horse_y;  
    cin >> n >> m >> horse_x >> horse_y;  
    
    // 创建棋盘并标记控制点  
    vector<vector<bool>> blocked(n+1, vector<bool>(m+1, false));  
    vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));  
    
    // 标记马的位置和控制点  
    blocked[horse_x][horse_y] = true;  
    for (int i = 0; i < 8; ++i) {  
        int nx = horse_x + dx[i];  
        int ny = horse_y + dy[i];  
        if (nx >= 0 && nx <= n && ny >= 0 && ny <= m) {  
            blocked[nx][ny] = true;  
        }  
    }  
    
    // 初始化起点  
    dp[0][0] = blocked[0][0]? 0 : 1;  
    
    // 处理第一列  
    for (int i = 1; i <= n; ++i) {  
        if (!blocked[i][0]) {  
            dp[i][0] = dp[i-1][0];  
        }  
    }  
    
    // 处理第一行  
    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) {  
        for (int j = 1; j <= m; ++j) {  
            if (!blocked[i][j]) {  
                dp[i][j] = dp[i-1][j] + dp[i][j-1];  
            }  
        }  
    }  
    
    cout << dp[n][m] << endl;  
    return 0;  
}

五、总结

本文通过动态规划解决“过河卒”问题，重点在于状态定义、边界初始化与马的控制点处理。代码利用vector简化边界判断，结合方向数组高效标记控制点，最终实现O(nm)时间复杂度。该解法对算法竞赛中的DP问题具有参考价值。