Description

Pocket Cube is a 3-D combination puzzle. It is a 2 × 2 × 2 cube, which means it is constructed by 8 mini-cubes. For a combination of 2 × 2 mini-cubes which sharing a whole cube face, you can twist it 90 degrees in clockwise or counterclockwise direction, this twist operation is called one twist step. 
Considering all faces of mini-cubes, there will be totally 24 faces painted in 6 different colors (Indexed from 0), and there will be exactly 4 faces painted in each kind of color. If 4 mini-cubes‘ faces of same color rely on same large cube face, we can call the large cube face as a completed face. 



Now giving you an color arrangement of all 24 faces from a scrambled Pocket Cube, please tell us the maximum possible number of completed faces in no more than N twist steps. 
Index of each face is shown as below: 

 

Input

Output

Sample Input

Sample Output

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<queue> 6 #include<algorithm> 7 #include<map> 8 #define INF 0x3f3f3f3f 9 #define M(a,b) memset(a,b,sizeof(a))10 11 using namespace std;12 13 int state[24];14 int change[6][24]={15     {6,1,12,3,5,11,16,7,8,9,4,10,18,13,14,15,20,17,22,19,0,21,2,23},16     {20,1,22,3,10,4,0,7,8,9,11,5,2,13,14,15,6,17,12,19,16,21,18,23},17     {1,3,0,2,23,22,4,5,6,7,10,11,12,13,14,15,16,17,18,19,20,21,9,8},18     {2,0,3,1,6,7,8,9,23,22,10,11,12,13,14,15,16,17,18,19,20,21,5,4},19     {0,1,11,5,4,16,12,6,2,9,10,17,13,7,3,15,14,8,18,19,20,21,22,23},20     {0,1,8,14,4,3,7,13,17,9,10,2,6,12,16,15,5,11,18,19,20,21,22,23},21 };22 23 int N;24 int ans;25 26 struct tube27 {28     int d[24];29     int cnt;30     tube(){}31 };32 tube st;33 tube trans(tube tmp,int k)34 {35     tube res;36 37     for (int i=0; i<24; i++)38     res.d[i]=tmp.d[change[k][i]];39 40     return res;41 }42 int count(tube tmp)43 {44     int res=0;45     if (tmp.d[0]==tmp.d[1] && tmp.d[1]==tmp.d[2] && tmp.d[2]==tmp.d[3]) res++;46     if (tmp.d[8]==tmp.d[9] && tmp.d[14]==tmp.d[15] && tmp.d[8]==tmp.d[14]) res++;47     if (tmp.d[6]==tmp.d[7] && tmp.d[7]==tmp.d[12] && tmp.d[12]==tmp.d[13]) res++;48     if (tmp.d[4]==tmp.d[5] && tmp.d[5]==tmp.d[11] && tmp.d[11]==tmp.d[10]) res++;49     if (tmp.d[16]==tmp.d[17] && tmp.d[17]==tmp.d[19] && tmp.d[19]==tmp.d[18]) res++;50     if (tmp.d[20]==tmp.d[21] && tmp.d[21]==tmp.d[22] && tmp.d[22]==tmp.d[23]) res++;51     return res;52 }53 54 void bfs()55 {56     queue<tube> q;57     q.push(st);58 //    map<tube,int> mp;59 //    mp[st]=1;60     ans=count(st);61     while(!q.empty())62     {63         tube now=q.front();64         q.pop();65         tube tmp;66         for (int i=0; i<6; i++)67         {68             tmp=trans(now,i);69             tmp.cnt=now.cnt+1;70 //            if (mp.find(tmp)!=mp.end())71 //            {72 //                mp[tmp]=1;73 //                ans=max(ans,count(tmp));74 //                if (tmp.cnt<num) q.push(tmp);75 //            }76             ans=max(ans,count(tmp));77             if (tmp.cnt<N) q.push(tmp);78         }79     }80 }81 82 int main()83 {84    //init();85    while(scanf("%d",&N)==1)86    {87        for(int i = 0;i<24;i++)88        {89             scanf("%d",&st.d[i]);90         }91         st.cnt=0;92         bfs();93        printf("%d\n",ans);94    }95    return 0;96 }