らての精進日記

修行をします

aoj0300:Floppy Cube

解法

一度の状態遷移で4つの状態に遷移するので、{\displaystyle 4^8}個くらい状態数があります。


連続で同じ場所を回転させるのは無駄なので、前回の遷移で回転させた場所を覚えておいて、次の遷移ではそこを回転させないようにすると状態数が{\displaystyle 3^8}個くらいに落ちます。

しかし、そのような工夫を特にしなくても普通に通ります。

{\displaystyle 4^8=2^{16}≒60000}
くらいなので、定数倍やN回解くことを考慮してもたぶん大丈夫です。


コード

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

int N;

int c[30];
int ans[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};
int change[4][10]={
    {0,27,1,28,2,29,14,15,18,20},
    {0,23,3,26,6,29,9,20,15,17},
    {6,21,7,22,8,23,12,17,9,11},
    {2,21,5,24,8,27,11,18,12,14},
};

bool isOk(){
    for(int i=0;i<30;i++)if(c[i]!=ans[i])return false;
    return true;
}

void changer(int i){
    for(int j=0;j<5;j++)swap(c[change[i][j*2]],c[change[i][j*2+1]]);
}

int dfs(int cnt=0){
    if(cnt>=8)return 8;
    if(isOk())return cnt;
    int ret=8;
    for(int i=0;i<4;i++){
        changer(i);
        ret=min(ret,dfs(cnt+1));
        changer(i);
    }

    return ret;

}
void solve(){
    for(int i=0;i<30;i++)cin>>c[i];


    cout<<dfs()<<endl;
}

int main(){
    cin>>N;
    while(N--)solve();
}