[蓝桥杯]解谜游戏-EW帮帮网

解谜游戏

题目描述

小明正在玩一款解谜游戏。谜题由 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的数量
颜色验证：
- 每组必须满足：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;
}

扩展性：
- 封装分组验证函数
- 支持动态分组规则（适应不同圈层大小）

[蓝桥杯]解谜游戏