L2-040 哲哲打游戏 (25 分)-PAT 团体程序设计天梯赛 GPLT

哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。

输入格式：
输入第一行是两个正整数 N 和 M (1≤N,M≤105)，表示总共有 N 个剧情点，哲哲有 M 个游戏操作。

接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是 Ki，表示剧情点 i 通过一些操作或选择能去往下面 Ki个剧情点；接下来有 Ki个数字，第 k 个数字表示做第 k 个操作或选择可以去往的剧情点编号。

最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：

0 表示哲哲做出了某个操作或选择，后面紧接着一个数字 j，表示哲哲在当前剧情点做出了第 j 个选择。我们保证哲哲的选择永远是合法的。
1 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j 个档位上。
2 表示哲哲进行了一次读取存档的操作，后面紧接着是一个数字 j，表示读取了放在第 j 个位置的存档。
约定：所有操作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100 个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即 ∑Ki）不超过 106。

输出格式：
对于每个 1（即存档）操作，在一行中输出存档的剧情点编号。

最后一行输出哲哲最后到达的剧情点编号。

输入样例：
10 11
3 2 3 4
1 6
3 4 7 5
1 3
1 9
2 3 5
3 1 8 5
1 9
2 8 10
0
1 1
0 3
0 1
1 2
0 2
0 2
2 2
0 3
0 1
1 1
0 2

输出样例：
1
3
9
10

样例解释：
简单给出样例中经过的剧情点顺序：

1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。

档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9 号剧情点。

分析：node表示存档信息格式，其中pos表示当前所在剧情点编号，Path表示当前的游戏内所走的路径。Edge[i]中储存第i个剧情点可通往的剧情编号，Save中储存存档信息，now表示当前所在剧情点。之后按题意模拟即可～

#include <bits/stdc++.h>
using namespace std;
struct node {
    int pos;
    vector<int> Path;
};
int n, m, now = 1;
vector<int> temp, Edge[100005];
vector<node> Save(105);
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int t2;
            scanf("%d", &t2);
            Edge[i].push_back(t2);
        }
    }
    temp.push_back(1);
    for (int i = 1; i <= m; i++) {
        int c, J;
        scanf("%d%d", &c, &J);
        if (c == 0) {
            temp.push_back(Edge[now][J-1]);
            now = Edge[now][J - 1];
        } else if (c == 1) {
            Save[J].pos = now;
            Save[J].Path = temp;
            printf("%d\n", now);
        } else {
            now = Save[J].pos;
            temp = Save[J].Path;
        }
    }
    printf("%d", temp.back());
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

struct node {

int pos;

vector<int> Path;

};

int n, m, now = 1;

vector<int> temp, Edge[100005];

vector<node> Save(105);

int main() {

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i++) {

int k;

scanf("%d", &k);

for (int j = 0; j < k; j++) {

int t2;

scanf("%d", &t2);

Edge[i].push_back(t2);

}

temp.push_back(1);

for (int i = 1; i <= m; i++) {

int c, J;

scanf("%d%d", &c, &J);

if (c == 0) {

temp.push_back(Edge[now][J-1]);

now = Edge[now][J - 1];

} else if (c == 1) {

Save[J].pos = now;

Save[J].Path = temp;

printf("%d\n", now);

} else {

now = Save[J].pos;

temp = Save[J].Path;

}

printf("%d", temp.back());

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版