QOJ.ac

QOJ

حد الوقت: 2 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تفاعلية

#3516. 地下城探索者

الإحصائيات

在著名的电子游戏《Wizards & Wyvern》中,主角发现自己身处某种迷宫结构中,必须找到出路。每一层关卡都由若干洞穴、平台、房间或其他有趣的地点组成,这些地点通过不同类型的路径相连。在每个地点,都有一个独特且可辨识的文物,英雄可以激活它。为了逃离某一层,玩家必须按正确的顺序激活正确的文物。隐藏在迷宫中的谜题可以帮助他通关。

第一个样例的迷宫概览。

你讨厌谜题,因此从网上获取了一张单层关卡的地图及其解法。你只需要找出这张地图是否代表你当前所在的关卡。

在地点之间穿梭时,玩家可以看到当前地点的文物以及所有通往外部的路径。游戏实现了 26 种不同类型的路径,例如铺砌道路(P)、桥梁(B)或土路(D)。在每个地点,所有通往外部的路径类型各不相同。

这是一个交互式问题。你不知道你的初始位置,但你总是可以决定走哪条路径。对于你访问的每个地点,你都会获知该处的文物名称以及通往外部的路径类型。你的任务是找出该关卡是否与你地图上的关卡匹配。

交互协议

你的程序将与一个名为 grader 的特殊程序进行交互。这意味着你的程序的输出会被发送给 grader,而 grader 的输出会被发送到你程序的标准输入。这种交互必须遵循特定的协议:

grader 首先发送地图的描述: 一个整数 $n$ ($2 \le n \le 1\,000$),表示地图上的地点数量。 $n$ 行,第 $i$ 行包含一个整数 $k$,后跟 $k$ 个对 $t_1 m_1, \dots, t_k m_k$,描述从地点 $i$ 通往外部的路径。每条路径由其类型 $t_j$($t_j$ 为大写字母)和目的地 $m_j$ ($1 \le m_j \le n, m_j \neq i$) 给出。

所有路径都是双向的,且在输入中出现两次,即每个方向各一次。你可以确信迷宫中所有地点都是从任何位置可达的。

随后,游戏按回合进行。在每一回合中,grader 会按以下格式发送你当前所在位置的描述: * 一行包含一个由小写字母组成的字符串 $a$ ($1 \le |a| \le 20$) 和一个由大写字母组成的字符串 $s$ ($1 \le |s| \le 26$),分别表示你在该地点看到的文物名称以及通往外部的路径描述。没有两个地点会有相同的文物。字符串 $s$ 中的所有字母各不相同且为大写,顺序不固定。再次进入同一地点时,顺序可能会发生变化。

你的程序必须做出以下响应之一: W c —— 你想沿着类型为 $c$ 的路径行走,其中 $c$ 是一个有效的路径类型字符。 R i —— 你确定该关卡与地图对应。整数 $i$ ($1 \le i \le n$) 应为你认为你当前所在的初始地图上的地点编号。 R ambiguous —— 该关卡与地图匹配,但匹配结果不唯一。 R no —— 该关卡与你的地图不对应。

在每次以 W 开头的有效响应后,grader 会给出你当前所在新地点的描述。你最多只能进行 $250\,000$ 次移动。在以 R 开头的响应后,游戏结束。如果你发送了无效响应,游戏结束,你的提交将被判为“Wrong Answer”。在你发送每条命令后,应刷新标准输出,以确保其被发送到游戏中。例如,在 C++ 中可以使用 fflush(stdout),在 Java 中使用 System.out.flush(),在 Python 中使用 sys.stdout.flush()

样例

输入格式 1

3
2 D 2 B 3
2 P 3 D 1
2 P 2 B 1
fountain DB
obelisk PD
crystals PB
fountain DB

输出格式 1

W D
W P
W B
R 1

输入格式 2

3
2 D 2 B 3
2 P 3 D 1
2 P 2 B 1
obelisk PD
fountain LD

输出格式 2

W D
R no

输入格式 3

2
2 P 2 D 2
2 D 1 P 1
fountain PD
obelisk PD
fountain PD

输出格式 3

W P
W D
R ambiguous

说明

在上述交互示例中,左侧为 grader 的输出,右侧为提交程序的一种可能的正确输出。两侧的空行仅用于强调请求和回答的时间顺序。grader 永远不会输出任何空行。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.