信息学奥林匹克竞赛指导：过河卒问题解析

题目背景

在信息学奥林匹克竞赛中，有一类经典的动态规划问题——过河卒。此题源自Noip2002，编号1314，旨在测试选手对路径计算和障碍规避算法的掌握情况。

题目描述

给定一个大小为n*m的棋盘，起点位于(0,0)，终点位于(n,m)。棋盘上存在一个敌方的‘马’，其位置由输入给出，且该‘马’及其可一步跳跃到达的所有点被视为不可通行。任务是计算出从起点到终点的所有可行路径数量，路径移动仅限于向右或向下。

输入说明

输入包括三个整数n、m和C点的坐标，分别代表棋盘的宽度、高度以及敌方‘马’的位置。注意，马的位置不会与起点或终点重合。

输出说明

输出从起点到终点的所有可行路径数量。

示例

输入样例

8 6 0 4

输出样例

1617

解题思路

对于此类问题，直接使用深度优先搜索（DFS）在较大规模的数据下会遇到超时的问题。因此，采用动态规划是一种更为高效的方法。动态规划的核心在于将大问题分解为小问题，并利用之前计算的结果来减少重复计算。具体到本题，可以通过定义一个二维数组f[i][j]来记录到达每个点(i,j)的路径数，同时使用另一个二维数组g[i][j]来标记该点是否为障碍点。对于每个非障碍点，其路径数等于其上方点和左侧点的路径数之和。对于障碍点，其路径数设为0。最后，f[n][m]即为所求的答案。

实现细节

考虑到路径数可能非常大，需要特别注意数据类型的选取以避免溢出。此外，初始化时需确保起点的路径数为1，即f[0][0]=1。对于边界点，如果它们不是障碍，则路径数同样设为1。最后，遍历整个棋盘，按照上述规则更新每个点的路径数，直至计算出最终结果。

参考代码

#include 
#define MAXM 25
#define MAXN 25
int g[MAXM][MAXN];
int dir[8][2] = {{-2,-1},{-1,-2},{2,-1},{1,-2},{2,1},{1,2},{-1,2},{-2,1}};
long long f[MAXM][MAXN];
int main() {
    int n, m, x, y;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    g[x][y] = 1; // 马所在位置
    f[0][0] = 1;
    for(int i = 0; i <8; i++) {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if(nx >= 0 && nx <= n && ny >= 0 && ny <= m)
            g[nx][ny] = 1; // 马的控制点
    }
    for(int i = 1; i <= n; i++) {
        if(g[i][0]) break;
        else f[i][0] = 1;
    }
    for(int i = 1; i <= m; i++) {
        if(g[0][i]) break;
        else f[0][i] = 1;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(!g[i][j]) f[i][j] = f[i-1][j] + f[i][j-1];
    printf("%lld\n", f[n][m]);
    return 0;
}