2014
02-24

# Rubiks Cube

Following the hype generated by Rubiks Cube Norwegian Open Championship arranged at NTNU this year, each and every student at NTNU has bought such a cube. The professors, however, are dismayed, because the students rather play with their cube instead of listening to the professors lectures.

One professor suddenly gets the idea that if he gives the students a program to solve their cubes they may lose interest in it, so that it will be possible to start teaching again. Of course, the professor don’t want to do the grunt work of programming, and you are the lucky assignee of this task.

The professor takes away your cube, locks you in a faraway laboratory and says that you won’t get out until you have written a program to solve Rubiks cube.

Luckily, the professor did not specify the size of the cube, so you decide to make the work slightly easier by solving the Rubiks 2  2  2 cube.

The first line of the input consists of a single number T, the number of test cases. Each test case consists of six lines describing the initial configuration of a cube, formatted exactly as in the example input. The characters used for colors are G, R, O, B, Y and W.

Each test case is followed by an empty line.

The first line of the input consists of a single number T, the number of test cases. Each test case consists of six lines describing the initial configuration of a cube, formatted exactly as in the example input. The characters used for colors are G, R, O, B, Y and W.

Each test case is followed by an empty line.

2
OO
OO
RR GG BB WW
RR GG BB WW
YY
YY
RR
RR
YY OO GG BB
OO GG BB YY
WW
WW

0
1

00 01
02 03
04 05 06 07 08 09 10 11
12 13 14 15 16 17 18 19
20 21
22 23

OO
OO
RR GG BB WW
RR GG BB WW
YY
YY

[O]
[R][G][B][W]
[Y]

#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<cstdlib>
using namespace std;

int cvr[6][12]={
{4,12,13,5,3,2,11,19,20,21,14,6},
{12,13,5,4,11,19,20,21,14,6,3,2},
{7,6,14,15,1,3,5,13,21,23,16,8},
{6,14,15,7,5,13,21,23,16,8,1,3},
{1,0,2,3,8,9,10,11,4,5,6,7},
{0,2,3,1,10,11,4,5,6,7,8,9}};

int block[8][3]={
{3,5,6},{1,7,8},{0,9,10},{2,4,11},
{12,19,20},{13,14,21},{15,16,23},{17,18,22}};

struct S{
char s[30];

friend bool operator< (const S& a,const S& b){
return strcmp(a.s,b.s)<0;
}

void change(){
map<char,char> col;
map<char,bool> flag;
col[s[17]]='B'; flag[s[17]]=true;
col[s[18]]='W'; flag[s[18]]=true;
col[s[22]]='Y'; flag[s[22]]=true;
for(int i=0;i<7;i++){
int cnt=0,sum=0,has=3;
if(flag[s[block[i][0]]]){cnt++;sum+=col[s[block[i][0]]];has-=0;}
if(flag[s[block[i][1]]]){cnt++;sum+=col[s[block[i][1]]];has-=1;}
if(flag[s[block[i][2]]]){cnt++;sum+=col[s[block[i][2]]];has-=2;}
if(cnt!=2) continue;
if(sum=='B'+'W') col[s[block[i][has]]]='O';
if(sum=='B'+'Y') col[s[block[i][has]]]='G';
if(sum=='Y'+'W') col[s[block[i][has]]]='R';
}
for(int i=0;i<24;i++){
s[i]=col[s[i]];
}
}
}s;
map<S,int> step;

void in(char &c){
c=getchar();
while(c<=32) c=getchar();
}

void bfs0(){
strcpy(s.s,"OOOORRGGBBWWRRGGBBWWYYYY");
step.clear();
step[s]=-1;

queue<pair<S,int> > que;
que.push(make_pair(s,0));
while(!que.empty()){
S u=que.front().first;
int d=que.front().second;
que.pop();
for(int i=0;i<6;i++){
S v=u;
for(int j=0;j<12;j++){
v.s[cvr[i][j]]=u.s[cvr[i^1][j]];
}
if(step[v]) continue;
step[v]=d+1;
if(d<6){
que.push(make_pair(v,d+1));
}
}
}
}

map<S,bool> vis;
int bfs1(){
s.change();

if(step[s]){
if(step[s]==-1) return 0;
else return step[s];
}
vis.clear();
vis[s]=true;

queue<pair<S,int> > que;
que.push(make_pair(s,0));
while(!que.empty()){
S u=que.front().first;
int d=que.front().second;
que.pop();
for(int i=0;i<6;i++){
S v=u;
for(int j=0;j<12;j++){
v.s[cvr[i][j]]=u.s[cvr[i^1][j]];
}
if(vis[v]) continue;
vis[v]=true;
if(step[v]){
if(step[v]==-1) return d+1;
else return step[v]+d+1;
}
que.push(make_pair(v,d+1));
}
}
return -1;
}

int main(){
bfs0();

int t;
scanf("%d",&t);
while(t--){
for(int i=0;i<24;i++){
in(s.s[i]);
}

int ans=bfs1();
printf("%d\n",ans);
}
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

4. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}