[数据结构与算法][NOIP2002 普及组] 过河卒

话不多说先上代码题解

#include<iostream>
#include<cstdlib>

using namespace std;

long long res[25][25];
bool map[25][25];

int main()
{
    res[1][1] = 1;
    int B_x,B_y,C_x,C_y;
    cin >> B_x >> B_y >> C_x >> C_y;
    ++B_x;
    ++B_y;
    ++C_x;
    ++C_y;
    map[C_x][C_y] = 1;
    map[C_x - 1][C_y - 2] = 1;
    map[C_x - 2][C_y - 1] = 1;
    map[C_x - 2][C_y + 1] = 1;
    map[C_x - 1][C_y + 2] = 1;
    map[C_x + 1][C_y + 2] = 1;
    map[C_x + 1][C_y - 2] = 1;
    map[C_x + 2][C_y + 1] = 1;
    map[C_x + 2][C_y - 1] = 1;
    for(int i = 1;i <= B_x;++i)
    {
        for(int j = 1;j <= B_y;++j)
        {
            if(!map[i][j] && (i != 1 || j != 1)) res[i][j] = res[i - 1][j] + res[i][j - 1];
        }
    }
    cout << res[B_x][B_y] << endl;
}

具体思路大致就是dp。

可以发现对于每一个点（x，y），只有可能是从左邻位置或者右邻位置过来的，即（x -1，y）和（x，y-1）,那么状态转移方程就很好列出了：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

卒的坐标是从0开始的，这对于第一行和第一列的数据来讲并不方便处理。因此我们可以考虑整体数组开大一点，坐标从1开始计数，这样数组索引为0时值为0不影响数据也不至于越界。

然后考虑马的位置，马走“日”字，即周围所有走一次“日”字能够到达的位置对其进行标记，声明一个map对相应位置进行记为1，返回布尔类型用于判断即可。

然后就从1开始一直到B点坐标进行一个遍历访问，更新dp数组即可。