学步园

BFS遍历翻转之后的状态，因为一共就654321个状态，不会TLE。

Trick 可以将六个面的数字映射成一个十进制数用来判断BFS是否被访问过，防止重复遍历。

本机debug了好久，BFS居然忘了pop()。。。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;


class dice
{
public:
    int ary[7];
    int step;
   // int value;
    dice()
    {
        memset(ary,0,sizeof(ary));
        step=0;
      //  value=0;
    }
    dice(int s)
    {
        memset(ary,0,sizeof(ary));
        step=s;
     //   value=v;
    }
};
dice a;
dice b;
queue<dice> q;
int ans;
int vis[1000000];
int done(dice d)//将每个dice上的组合map成一个整数，最大为654321，用于判断BFS是否访问过
{
    int num=0;
    for(int i=1;i<=6;i++)
    {
        num=num*10+d.ary[i];
    }
    return num;
}
bool same(dice d)
{
    for(int i=1;i<=6;i++)
    {
       // cout<<d.ary[i]<<" "<<b.ary[i]<<endl;
        if(d.ary[i]!=b.ary[i])
        {
            return false;
        }
    }
     return true;
}
dice rotated(int n,dice d)
{
    dice c;
    if(n==1)//left
    {
        int tmp=d.ary[3];
        c.ary[3]=d.ary[1];
        c.ary[1]=d.ary[4];
        c.ary[4]=d.ary[2];
        c.ary[2]=tmp;
        c.ary[5]=d.ary[5];//don not forget to copy these two
        c.ary[6]=d.ary[6];
    }
    else if(n==2)//right
    {
        int tmp=d.ary[2];
        c.ary[1]=d.ary[3];
        c.ary[4]=d.ary[1];
        c.ary[2]=d.ary[4];
        c.ary[3]=tmp;
        c.ary[5]=d.ary[5];
        c.ary[6]=d.ary[6];
    }
    else if(n==3)//front
    {
        int tmp=d.ary[5];
        c.ary[5]=d.ary[1];
        c.ary[1]=d.ary[6];
        c.ary[6]=d.ary[2];
        c.ary[2]=tmp;
        c.ary[3]=d.ary[3];
        c.ary[4]=d.ary[4];
    }
    else if(n==4)//back
    {
        int tmp=d.ary[5];
        c.ary[6]=d.ary[1];
        c.ary[2]=d.ary[6];
        c.ary[5]=d.ary[2];
        c.ary[1]=tmp;
        c.ary[3]=d.ary[3];
        c.ary[4]=d.ary[4];
    }
    return c;
}
void bfs()
{
    memset(vis,0,sizeof(vis));
    ans=-1;
    while(!q.empty()) q.pop();
    a.step=0;
    q.push(a);
    vis[done(a)]=1;
    dice tmp;
    //cout<<done(a)<<endl;
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        if(same(tmp))
        { //cout<<done(tmp)<<" "<<tmp.step<<endl;

            ans=tmp.step;
             //cout<<ans<<" ";
            break;
        }
        for(int i=1;i<=4;i++)
        {
            dice d=rotated(i,tmp);
            if(vis[done(d)]==0)
            {
                //cout<<i<<" "<<done(d)<<endl;
                d.step=tmp.step+1;
                q.push(d);
                vis[done(d)]=1;//否则回到原先的状态会重复遍历
                //cout<<d.step<<endl;
            }
        }
    }
    printf("%d\n",ans);
}
int main()
{
    freopen("input.txt","r",stdin);
   // freopen("data.txt","r",stdin);
   // freopen("out1.txt","w",stdout);
   int t;
   while(scanf("%d",&t)!=EOF)
   {
       a.ary[1]=t;
       for(int i=2;i<=6;i++)
       {
           scanf("%d",&a.ary[i]);
       }
       for(int i=1;i<=6;i++)
       {
           scanf("%d",&b.ary[i]);
       }
       bfs();

   }

    return 0;
}