[AOJ] No. 0300 フロッピーキューブ

2020年1月1日2020年12月17日

問題

方針

パズルは最大でも \( 8 \) 回の操作で解くことができるので、\( 4^7 \) 通りのパターンを調べれば良いです。したがって、深さ優先探索を行い、実際にシミュレーションを行います。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ans = 8;
int p[30];
int q[30] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 4,
             4, 6, 6, 6, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3};
bool flag;
void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void rot(int i) {
    if (i == 0) {
        swap(p[0], p[27]);
        swap(p[1], p[28]);
        swap(p[2], p[29]);
        swap(p[14], p[15]);
        swap(p[18], p[20]);
    } else if (i == 1) {
        swap(p[6], p[21]);
        swap(p[7], p[22]);
        swap(p[8], p[23]);
        swap(p[12], p[17]);
        swap(p[9], p[11]);
    } else if (i == 3) {
        swap(p[0], p[23]);
        swap(p[3], p[26]);
        swap(p[6], p[29]);
        swap(p[9], p[20]);
        swap(p[15], p[17]);
    } else {
        swap(p[2], p[21]);
        swap(p[5], p[24]);
        swap(p[8], p[27]);
        swap(p[11], p[18]);
        swap(p[12], p[14]);
    }
}

void solve(int n) {
    if (n == 8) return;
    
    flag = true;
    for (int i = 0; i < 30; i++) {
        if (p[i] != q[i]) flag = false;
    }
    if (flag) {
        ans = min(ans, n);
        return;
    }
    for (int i = 0; i < 4; i++) {
        rot(i);
        solve(n + 1);
        rot(i);
    }
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 30; j++) {
            cin >> p[j];
        }
        ans = 8;
        flag = false;
        solve(0);
        cout << ans << "\n";
    }
    return 0;
}