aoj0300:Floppy Cube
解法
一度の状態遷移で4つの状態に遷移するので、個くらい状態数があります。
連続で同じ場所を回転させるのは無駄なので、前回の遷移で回転させた場所を覚えておいて、次の遷移ではそこを回転させないようにすると状態数が個くらいに落ちます。
しかし、そのような工夫を特にしなくても普通に通ります。
くらいなので、定数倍や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(); }