P8700 解谜游戏

· · 题解

P8700 [蓝桥杯 2019 国 B] 解谜游戏

题意简述

现有内中外三圈塑料棒，根数分别为 4,8,12 根。有黄红绿三种颜色的塑料棒，根数分别为 4,8,12 根。有三种操作，求是否能达成绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈的目标。

题目分析

先考虑搜索，每个状态有三种操作，呈指数型增长。况且判断状态是否重复就会牺牲大量的时间，就会超时，不可取。

我们注意到这一题只让我们求可行性，而不在乎具体的方案。要使所有颜色移到对应位置，我们只需要操作三。而操作一二都只是在选择操作三的位置，所以每个操作三都是有必然的联系的。

内圈周期为 4，中圈周期为 8，外圈周期为 12，共同的周期为 4。所以对于内圈的一个塑料棒，如下图，与其他 5 个塑料棒是固定不变的，只能与这 5 个交换。

若这 6 个塑料棒的的颜色刚好为 3 个绿色，2 个红色和 1 个黄色时，操作三是一定可以变成目标状态的：否则无论怎么交换，始终是那些颜色，不可能到达目标状态的。

所以具体的做法是枚举内圈的 4 个塑料棒，再开个桶记录下这 6 个塑料棒的颜色，再判断下即可，详细见代码。

代码

#include <bits/stdc++.h>
using namespace std;
int t, cnt[100];
string a, b, c;
int main() {
    cin >> t;
    while (t--) {
        cin >> a >> b >> c;
        bool flag = 1;
        for (int i = 0; i < 4; ++i) {
            memset(cnt, 0, sizeof(cnt));//清空桶 
            ++cnt[a[i]], ++cnt[b[i]], ++cnt[c[i]];
            ++cnt[a[i+4]], ++cnt[a[i+8]], ++cnt[b[i+4]];//统计6个塑料棒的颜色 
            if (cnt['Y'] != 1 || cnt['R'] != 2 || cnt['G'] != 3) {//判断条件 
                flag = 0;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << '\n';
    }
    return 0;
}