首页 > 搜索 > BFS搜索 > HDU 2953-Rubiks Cube-BFS-[解题报告]HOJ
2014
02-24

HDU 2953-Rubiks Cube-BFS-[解题报告]HOJ

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

二阶魔方旋转,数据比较大,而且六面均可旋转(与HDU3459不同),结束状态不确定(与HDU2691不同),status里面各种WA,TLE,MLE,只有一人AC,果断膜拜,然后标记为神题就没去看了,后来看了那人代码,方法比较巧妙,但也并不是什么高深难懂的算法,可以说是双广+预处理

对每个面标号一下,我们用数字表示小面,字母表示颜色,用[字母]表示大面,如下

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]
  
首先我们可以想到,一个面的顺时针旋转相当于他的相对面逆时针旋转,这样我们可以将六个面的旋转转化为三个面的旋转,比如说我们对于[R]面的顺时针旋转就相当于对[B]面的逆时针旋转,而且这样步数是不会增大的,而状态减少了许多。
 

然后我们去找魔方的特殊性,二阶魔方的24个面并不是独立的,从魔方结构就能看出一个二阶魔方是分为8个小块的,每个块三种颜色,比如说图中的(3,5,6)是在同一块上,(1,7,8)是在同一块上,这样我们根据他的特殊性从每一个块去分析

 
我们只做[R][G][O]面的正逆旋转,这样的话(17,18,22)这一块的是不会移动的,即[B][W][Y]这三个面的最终颜色是确定的,然后再去扩展,与B和W在同一块里的除了Y之外还有O,B和Y还有G,Y和W还有R。按照上面所说的:我们将要求的魔方中的17 18 22三面分别变为B W Y,然后根据每块的相连关系将另外三面都重新染色,这样我们就将每一个魔方都转化为最终状态都相同情况了
  
然后的做法就很简单了,我们可以从一个状态开始扩展做预处理,但是保存全部状态内存消耗太大,我们可以只预处理出7层情况(二阶魔方最多需要14步到达最终状态),然后对每一个魔方,将它进行重新染色后进行广搜,搜到一个已经预处理过的状态时就返回答案,答案为两边步数之和,这样这题就搞定了~~


#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);
     }
 }

解题参考:http://www.cnblogs.com/ambition/archive/2011/08/24/Rubiks_Cube.html


  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;
    }