202301G 华小科的旅行开始了 题解

· · 题解

[语言月赛202301] 华小科的旅行开始了 题解

Source & Knowledge

2023 年 1 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

给定 n, m，起点以及「任务指引」。华小课从 (s _ x, s _ y) 出发，当当前点任务指引为 (0, 0) 时代表旅程停止，否则前往当前点任务指引所指的点。依次输出从旅程开始到旅程停止访问的各个点。

解析

使用 n \times 2m 的数组来存储本题的坐标可能会在计算下标等等方面比较麻烦。这里提供一种比较方便的存储数据的方式。

std::pair 可以将 2 个数据组合成 1 个数据并进行储存。它的实现是一个结构体，主要的两个成员变量是 first 与 second。

具体的，使用时，我们可以使用 pair<?, ?> 设立变量。这里的 ? 可以替换为 int 等数据类型。建立时，可以使用 make_pair(?, ?) 函数。这里的 ? 需要替换为对应的变量。访问时，直接访问 pair 变量.first 与 pair 变量.second 即可。

使用例：

using namespace std;
pair<int, int> a = make_pair(3, 4);
cout << a.first << " " << a.second << endl;

输出结果为 3 4。

当然，我们同样可以用一个自定义的结构体实现相同的功能。

struct Pair { int first, second; };

在后续的代码中，同样引用成员变量 first 与 second 即可。

对于坐标的存储，我们可以使用 pair 类型的数组来记录。

#define pii pair<int, int>
pii a[1005][1005];
for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        cin >> a[i][j].first >> a[i][j].second;
    }
}

在访问时，我们使用两个 int 变量 x, y 记录当前位置，使用 while 语句进行遍历输出即可。

每一次，我们读取到 a[x][y] 所存储的 pair 类型变量 v，并将 x 赋值为 v.first，将 y 赋值为 v.second 即可。循环的终止条件为 x, y 为 0。

核心代码如下：

int x = sx, y = sy;
while (x && y) {
    cout << x << " " << y << endl;
    pii cur = a[x][y];
    x = cur.first, y = cur.second;
}

视频题解

完整代码请在视频中查看。