信息奥赛题解｜过河卒

🚀 题目浏览

【题目描述】

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，$A$ 点 $(0, 0)$、$B$ 点 $(n, m)$，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

【输入】

一行四个正整数，分别表示 $B$ 点坐标和马的坐标。

【输出】

一个整数，表示所有的路径条数。

【输入样例】

6 6 3 3

【输出样例】

【数据范围】

$1 \le n, m \le 20$，$0 \le$ 马的坐标 $\le 20$。

【原题链接】

https://www.luogu.com.cn/problem/P1002

☘️ 题解分析

本题是「单点移动路线方案数」问题的经典题目之一，在上题「移动路线」的基础上，增加了障碍点的条件。（「移动路线」题目链接：信息奥赛题解｜移动路线 / 备用站点：信息奥赛题解｜移动路线）

我们只需要额外设置一个状态数组 vis，存储某个点是否为障碍点即可，剩下的思路和上题一致。

🍉 代码精简小提示：

本题可以用两个数组，存储马可能跳的点的横坐标/纵坐标变化值，这样只需要循环一次，就能把所有马能跳到的障碍点的 vis 值置为 1
题目中起点是从 $(0,0)$ 开始，而传统的「移动路线」问题是从 $(1,1)$ 开始，所以可以在坐标读入的时候全部 +1。但是由于本题在计算马的坐标时，可能遇到 -2 越界的问题，所以干脆整体 +2，起点从 $(2,2)$ 开始，会精简不少代码。

🧑🏻‍💻 C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 30;

//马可能会跳的点
int horse_x[] = {0, -1, -1, -2, -2, +1, +1, +2, +2};
int horse_y[] = {0, +2, -2, +1, -1, +2, -2, -1, +1};
//vis数组存储过河状态
int vis[N][N];
//a数组存储路线方案数
long long a[N][N];

int n, m, x, y;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    //由于题目起点从（0，0）开始，且马的坐标跳跃坐标有 -2，所以不妨所有坐标点均 +2，防止越界
    cin >> n >> m >> x >> y;
    n += 2;
    m += 2;
    x += 2;
    y += 2;

    //将马可能走到的点的状态置为1
    for (int i = 0; i <= 8; ++i) {
        vis[x + horse_x[i]][y + horse_y[i]] = 1;
    }


    //计算a数组
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= m; ++j) {
            //此时起点为（2，2）
            if (i == 2 && j == 2)
                a[i][j] = 1;

            //遇到了障碍点
            else if (vis[i][j] == 1)
                a[i][j] = 0;

            else
                a[i][j] = a[i - 1][j] + a[i][j - 1];
        }
    }
    //输出结果
    cout << a[n][m] << endl;

    return 0;
}