[NOIP2002 普及组] 过河卒 题解

skystars

【题解】这题是较基础的动态规划问题
代码如下：

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

long long f[25][25]; // 注意要开long long，否则会炸
// f[x][y]表示从原点走到(x,y)的路径数量
int dx[] = { -2,-2,-1,-1,1,1,2,2 }; // 位置偏移数组
int dy[] = { -1,1,-2,2,-2,2,-1,1 };
int x, y; // 马的坐标
bool isctrl(int xx, int yy) { // 判断是否在马的控制范围内，在返回true（1），不在返回false（0）
        if (x == xx && y == yy) return true;
        for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (xx == nx && yy == ny) return true;
        }
        return false;
}
int main() {
        int n, m;
        scanf("%d%d%d%d", &n, &m, &x, &y);
        f[0][0] = !isctrl(0, 0); // 初始化，若原点不在马的控制范围内，则初始化为1，否则为0
        for (int i = 1; i <= n; i++)
                if (!isctrl(i, 0)) // 注意
                        f[i][0] = f[i - 1][0]; // 千万不要写成f[i][0] = 1！因为它上面的点有可能在马的控制范围内
        for (int i = 1; i <= m; i++)
                if (!isctrl(0, i)) // 同样需要注意
                        f[0][i] = f[0][i - 1];
        for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                        if (!isctrl(i, j)) // 判断该点是否在马的控制范围内
                                f[i][j] = f[i][j - 1] + f[i - 1][j]; // 该点的路径数等于它左边的点和它上面的点的路径数和
                }
        }
        printf("%lld", f[n][m]); // 输出结果，注意这是long long类型，必须写成%lld
        return 0;
}