湖南NOI2018选拔赛第二试：寻宝游戏与路径规划

本题是针对 NOI2018 湖南省组队选拔赛的第二试中的编程题目，主要涉及C++或C语言的算法设计。题目主题是“游戏”，具体任务是解决小G与小H玩的寻宝游戏。游戏场景是$n$个房间排成一列，每个房间之间有门相连，部分门被锁上，需要相应的钥匙才能开启。题目提供了以下关键信息： 1. **输入与限制**： - 输入包含三个整数：房间总数$n$、锁的数量$p$以及询问次数$q$。 - 提供一个描述钥匙分布的序列，表示每把锁对应的钥匙所在房间。 - 有$p$次指令，每次指令指定小H从某个房间出发寻找宝藏。 - 时间限制：每个测试点有1秒的时间限制。 - 内存限制：对于C++和C语言，内存上限为512M，Pascal语言为256M。 2. **任务**： - 根据小G提供的钥匙信息，分析出一条或多条可行的路线，使得小H能够按照指示依次通过锁住的门。 - 需要编写程序来模拟这些路径，处理指令并检查是否能按顺序找到所有钥匙。 3. **输出**： - 对于每个询问，输出一条或多条可行的路线，如示例中提到的“2 3 2 1 2 3 4 5”这样的路线序列。 - 结果比较方式包括字符串比较和整数比较，具体取决于题目要求。 4. **提交要求**： - 提交的源代码需根据指定的语言（C++, C, 或 Pascal）分别命名为game.cpp/perm.cpp/road.cpp等。 - 编译时需要遵循特定的命令，例如使用g++或gcc等编译器。 - 代码需按照NOI规范提交，包括子目录的命名和文件名的大小写要求。 5. **注意事项**： - 程序运行在NOILinux环境下，特别强调了选手必须在规定的工作目录下操作，并且源程序必须清晰组织在对应的子目录内。 6. **评分标准**： - 第1题“游戏”为100分，时间限制为2秒，对代码效率和正确性有较高要求。 这个题目需要参赛者设计一个算法来解决小H如何根据钥匙分布和指令找到宝藏的路径问题，同时考虑时间和空间效率，并按照给出的规则提交正确的代码。