[蓝桥杯]解谜游戏
解谜游戏
题目描述
小明正在玩一款解谜游戏。谜题由 24 根塑料棒组成，其中黄色塑料棒 4 根，红色 8 根，绿色 12 根 (后面用 Y 表示黄色、R 表示红色、G 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 12 根，中圈 8 根，内圈 4 根。
小明可以进行三种操作：
-
将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：GYRYGRYGRGGG、 YRGRGGRR 和 RGGG。
-
将三圈塑料棒都逆时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么逆时针旋转一次之后，外圈、中圈、内圈依次变为：RYGRYGRGGGGY、 GRGGRRYR 和 GGRG。
-
将三圈 0 点位置的塑料棒做一个轮换。具体来说：外圈 0 点塑料棒移动到内圈 0 点，内圈 0 点移动到中圈 0 点，中圈 0 点移动到外圈 0 点。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么轮换一次之后，外圈、中圈、内圈依次变为：RRYGRYGRGGGG、GGRGGRRY 和 YGGR。
小明的目标是把所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。给定初始状态，请你判断小明是否可以达成目标？
输入描述
第一行包含一个整数 T (1≤T≤100)T (1≤T≤100)，代表询问的组数。
每组询问包含 3 行：
第一行包含 12 个大写字母，代表外圈从 0 点位置开始顺时针每个塑料棒的颜色。
第二行包含 8 个大写字母，代表中圈从 0 点位置开始顺时针每个塑料棒的颜色。
第三行包含 4 个大写字母，代表内圈从 0 点位置开始顺时针每个塑料棒的颜色。
输出描述
对于每组询问，输出一行 YES 或者 NO，代表小明是否可以达成目标。
输入输出样例
示例
输入
2
GYGGGGGGGGGG
RGRRRRRR
YRYY
YGGGRRRRGGGY
YGGGRRRR
YGGG
输出
YES
NO
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 264 | 总提交次数: 326 | 通过率: 81%
难度: 困难 标签: 2019, 思维, 国赛
算法思路
该解谜游戏的核心在于发现塑料棒的分组特性[1][2][3]。通过分析操作特性可得：
- 分组原理：24根塑料棒可分为4个固定分组（每组6根）
- 每组包含：内圈1根 + 中圈2根 + 外圈3根
- 分组依据：位置索引模4相同的塑料棒属于同一组
组0：内圈[0]、中圈[0][4]、外圈[0][4][8] 组1：内圈[1]、中圈[1][5]、外圈[1][5][9] 组2：内圈[2]、中圈[2][6]、外圈[2][6][10] 组3：内圈[3]、中圈[3][7]、外圈[3][7][11] - 操作特性：
- 旋转操作：只改变组内塑料棒的位置，不改变分组组成
- 轮换操作：仅在组0内交换塑料棒，不改变颜色总数
- 目标状态要求：每组必须含1黄(Y)、2红(R)、3绿(G)
C++代码实现
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;int main() {int T;cin >> T;while (T--) {string outer, middle, inner;cin >> outer >> middle >> inner;bool possible = true;// 检查4个分组for (int i = 0; i < 4; i++) {unordered_map<char, int> count;// 统计当前组的颜色count[inner[i]]++; // 内圈1根count[middle[i]]++; // 中圈第1根count[middle[i + 4]]++; // 中圈第2根count[outer[i]]++; // 外圈第1根count[outer[i + 4]]++; // 外圈第2根count[outer[i + 8]]++; // 外圈第3根// 验证颜色分布if (count['Y'] != 1 || count['R'] != 2 || count['G'] != 3) {possible = false;break;}}cout << (possible ? "YES" : "NO") << endl;}return 0;
}代码解析
- 输入处理：
outer（12字符）、middle（8字符）、inner（4字符）存储三圈颜色
- 分组检查：
- 循环遍历4个分组（
i=0到3） - 使用
unordered_map统计每组内Y/R/G的数量
- 循环遍历4个分组（
- 颜色验证：
- 每组必须满足：
Y=1,R=2,G=3 - 任一组不满足立即终止并返回NO
- 每组必须满足：
- 输出结果：
- 所有组满足条件输出"YES"，否则"NO"
实例验证
样例1输入：
GYGGGGGGGGGG
RGRRRRRR
YRYY分组验证：
| 组号 | 内圈 | 中圈 | 外圈 | Y | R | G | 是否满足 |
|---|---|---|---|---|---|---|---|
| 0 | Y | [R,R] | [G,G,G] | 1 | 2 | 3 | ✅ |
| 1 | R | [G,R] | [Y,G,G] | 1 | 2 | 3 | ✅ |
| 2 | Y | [R,R] | [G,G,G] | 1 | 2 | 3 | ✅ |
| 3 | Y | [R,R] | [G,G,G] | 1 | 2 | 3 | ✅ |
| 输出：YES（实际符合） |
样例2输入：
YGGGRRRRGGGY
YGGGRRRR
YGGG分组0验证：
- 内圈[0]=Y, 中圈[0]=Y/[4]=R, 外圈[0]=Y/[4]=R/[8]=G
- Y:3, R:2, G:1 → 不满足
输出：NO（实际符合）
测试点设计
- 边界测试：
- 全目标状态（12G外圈/8R中圈/4Y内圈）
- 全部分组错误状态
- 特殊分布：
- 颜色集中在特定组（如组0有3个Y）
- 颜色跨组不均匀（某组缺R多G）
- 极端操作：
- 执行最大轮换次数后的状态
- 旋转后颜色重组状态
优化建议
- 性能优化：
- 每组检查提前终止：发现不满足立即跳出循环
- 使用数组代替map：
int color[3]（Y/R/G对应0/1/2）
- 代码健壮性：
- 添加输入验证：检查字符串长度和合法字符
if (outer.length() != 12 || middle.length() != 8 || inner.length() != 4) {cerr << "Invalid input length";continue; } - 扩展性：
- 封装分组验证函数
- 支持动态分组规则（适应不同圈层大小）