魔方(cube.cpp)

題目描述：

給出一個二階魔方，保證 N 步以內能夠還原?！斑€原”被定義為每個面均為純色。

請給出，操作編號字典序最小，且不存在同類操作相鄰，的還原方案。

輸入格式：

第一行一個正整數N，表示最多步數。

接下來24個整數，按上圖的順序依次給出C_i，C_i∈{1,2,3,4,5,6}。

輸出格式：

一行，t個用空格隔開的正整數，表示復原的最小字典序操作序列，要求0 < t ? N。

最后一個數后無空格，數據保證輸入魔方是打亂的。

注:(1,2,3) 雖然長度長于(2,3)，但字典序更小。

樣例讀入：

2

1 1 1 1

4 4 2 2

6 6 3 3

3 3 6 6

5 5 5 5

4 4 2 2

樣例輸出：

2

樣例解釋：

因為不能類別相同的操作相鄰，所以只有2種操作方式可以在兩步內復原此時的魔方：(2),(17)，故字典序最小的為(2)。

數據范圍：

對于 20% 的數據，保證 N = 1

對于 40% 的數據，保證 N ? 3

對于另20%的數據，保證 N ? 6，且保證答案只用到前6種操作

對于100% 的數據，保證 N ? 7

題解：一開始看到數據范圍還以為是狀態壓縮，將魔方的每個狀態表示出來，結果發現不對。其實就是大模擬，如果每次枚舉18個操作，時間復雜度是O(n^18)，顯然會超時，只能拿60分。其實不難發現，不管怎樣，答案中的操作只能在1~9之間，比如底面順時針90度=頂面順時針270度，底面180度=頂面180度，底面270度=頂面90度。所以只用枚舉一面即可，于是就AC了。

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int n; int tag[20]; int work[30],flag=0,opt[30];int fa=0; unsigned long long get_hash() {fa++;unsigned long long Hash=0;for(int i=1;i<=8;i++) Hash=Hash*11+work[i];return Hash; } void init() {for(int i=1;i<=3;i++) tag[i]=tag[18-i+1]=1;for(int i=4;i<=6;i++) tag[i]=2;for(int i=7;i<=9;i++) tag[i]=3;for(int i=10;i<=12;i++) tag[i]=2;for(int i=13;i<=15;i++) tag[i]=3; } void change_(int id) {int a,b,c;switch(id){case 1:{//dinga=work[5];b=work[6];c=work[1];work[5]=work[13];work[6]=work[14];work[13]=work[24];work[14]=work[23];work[23]=work[10];work[24]=work[9];work[9]=a;work[10]=b;work[1]=work[3];work[3]=work[4];work[4]=work[2];work[2]=c;break;}case 2:{swap(work[5],work[24]);swap(work[6],work[23]);swap(work[13],work[9]);swap(work[14],work[10]);swap(work[1],work[4]);swap(work[2],work[3]);break;}case 3:{a=work[5];b=work[6];c=work[1];work[5]=work[9];work[6]=work[10];work[9]=work[24];work[10]=work[23];work[23]=work[14];work[24]=work[13];work[13]=a;work[14]=b;work[1]=work[2];work[2]=work[4];work[4]=work[3];work[3]=c;break;}case 4:{a=work[1];b=work[3];c=work[9];work[1]=work[21];work[3]=work[23];work[21]=work[17];work[23]=work[19];work[17]=work[5];work[19]=work[7];work[5]=a;work[7]=b;work[9]=work[11];work[11]=work[12];work[12]=work[10];work[10]=c;break;}case 5:{swap(work[1],work[17]);swap(work[3],work[19]);swap(work[5],work[21]);swap(work[7],work[23]);swap(work[9],work[12]);swap(work[10],work[11]);break;}case 6:{a=work[1];b=work[3];c=work[9];work[1]=work[5];work[3]=work[7];work[5]=work[17];work[7]=work[19];work[17]=work[21];work[19]=work[23];work[21]=a;work[23]=b;work[9]=work[10];work[10]=work[12];work[12]=work[11];work[11]=c;break;}case 7:{a=work[3];b=work[4];c=work[5];work[3]=work[12];work[4]=work[10];work[10]=work[17];work[12]=work[18];work[17]=work[15];work[18]=work[13];work[13]=a;work[15]=b;work[5]=work[7];work[7]=work[8];work[8]=work[6];work[6]=c;break;}case 8:{swap(work[3],work[18]);swap(work[4],work[17]);swap(work[13],work[12]);swap(work[15],work[10]);swap(work[5],work[8]);swap(work[6],work[7]);break;}case 9:{a=work[3];b=work[4];c=work[5];work[3]=work[13];work[4]=work[15];work[13]=work[18];work[15]=work[17];work[17]=work[10];work[18]=work[12];work[10]=b;work[12]=a;work[5]=work[6];work[6]=work[8];work[8]=work[7];work[7]=c;break;}} } void dfs(int dep,int last) {bool cct=0;for(int i=0;i<6;i++){int tmp=work[(i*4)+1];for(int j=1;j<=4;j++)if(work[(i*4)+j]!=tmp){cct=1;break;}if(cct) break;}if(!cct){flag=1;dep--;for(int i=1;i<dep;i++) printf("%d ",opt[i]);printf("%d\n",opt[dep]);return ;}if(dep==n+1) return ;int ccr[50];for(int i=0;i<6;i++)for(int j=1;j<=4;j++)ccr[(i*4)+j]=work[(i*4)+j];for(int i=0;i<=2;i++){if(last==i) continue;for(int j=(i*3+1);j<=(i+1)*3;j++){if(flag) return ;change_(j);opt[dep]=j;dfs(dep+1,i);if(flag) return ;for(int k=0;k<6;k++)for(int fe=1;fe<=4;fe++)work[(k*4)+fe]=ccr[(k*4)+fe];}} } int main() { // freopen("cube.in","r",stdin); // freopen("cube.out","w",stdout);init();int x;scanf("%d",&n);for(int i=0;i<6;i++)for(int j=1;j<=4;j++)scanf("%d",&x),work[(i*4)+j]=x;dfs(1,-1);return 0; }

總結

以上是生活随笔為你收集整理的魔方 大模拟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。