はまやんはまやんはまやん

hamayanhamayan's blog

フロッピーキューブ [パソコン甲子園2014 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0300?year=2014

考察過程

1. 操作がやばいので、操作の実装以外はそんなに難しくないのでは?
2. よく見ると最大8回で揃うようなので、操作は7回まで見ればいい(7回操作してできなかったら8回が答え)
3. 毎回4通りの操作があるので、4^7だが、これは余裕
4. BFSをすればいいのだが、遷移がやばいので頑張る
5. c++なら状態はvectorでもてば、setもqueueもいける

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0300/judge/3156503/C++14

実装が厳しいので頑張る。
check(v) := 全面揃っているか確認する
回転はswapを使うと、5回のswapで実現できる。
何をswapするかで添え字を入れておこう。
添字を2次元配列で管理しておけば、ループで4通りの操作を実現できる。

int N;
//---------------------------------------------------------------------------------------------------
int check(vector<int> &v) {
    rep(i, 0, 9) if (v[0] != v[i]) return 0;
    rep(i, 9, 12) if (v[9] != v[i]) return 0;
    rep(i, 12, 15) if (v[12] != v[i]) return 0;
    rep(i, 15, 18) if (v[15] != v[i]) return 0;
    rep(i, 18, 21) if (v[18] != v[i]) return 0;
    rep(i, 21, 30) if (v[21] != v[i]) return 0;
    return 1;
}
pair<int, int> E[4][5] = {
    {{7,22},{8,23} ,{9,24} ,{18,13} ,{10,12} }
    ,{ {3 , 22},{ 6, 25} ,{ 9, 28} ,{ 12, 19} ,{13 ,15 } }
    ,{ {1 , 24},{ 4,27 } ,{7 ,30 } ,{ 10,21 } ,{16 , 18} }
    ,{ {1 ,28 },{2 ,29 } ,{3 , 30} ,{21 ,19 } ,{15 ,16 } }
};
//---------------------------------------------------------------------------------------------------
int solve() {
    vector<int> v;
    rep(i, 0, 30) { int p; cin >> p; v.push_back(p); }

    set<vector<int>> done;
    if (check(v)) return 0;
    queue<vector<int>> que;

    done.insert(v);
    que.push(v);
    rep(i, 1, 8) {
        queue<vector<int>> que2;

        while (!que.empty()) {
            vector<int> q = que.front(); que.pop();

            rep(j, 0, 4) {
                vector<int> qq = q;
                rep(k, 0, 5) swap(qq[E[j][k].first - 1], qq[E[j][k].second - 1]);
                if (done.count(qq)) continue;
                if (check(qq)) return i;
                que2.push(qq);
                done.insert(qq);
            }
        }

        swap(que, que2);
    }
    return 8;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(_, 0, N) cout << solve() << endl;
}