[bfs]hdoj 5012

5454 ワード

おおよその意味
2つの色子を与えて、1つ目の色子が何回反転した後に2つ目の色子になることができるかを聞きます
 
大まかな考え方:
暴力は乗り越えられる
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
class nod{
public :
    int face[6];
    int res;
}aa1,aa2;
int vis[7][7][7][7][7][7],ans,num[6];
void turn1(nod& node){
    int i;
    int mark[6];
    for(i=0;i<6;i++){
        mark[i]=node.face[i];
    }
    node.face[0]=mark[3];
    node.face[1]=mark[2];
    node.face[2]=mark[0];
    node.face[3]=mark[1];
    node.face[4]=mark[4];
    node.face[5]=mark[5];
}
void turn2(nod& node){
    int i;
    int mark[6];
    for(i=0;i<6;i++){
        mark[i]=node.face[i];
    }
    node.face[0]=mark[2];
    node.face[1]=mark[3];
    node.face[2]=mark[1];
    node.face[3]=mark[0];
    node.face[4]=mark[4];
    node.face[5]=mark[5];
}
void turn3(nod& node){
    int i;
    int mark[6];
    for(i=0;i<6;i++){
        mark[i]=node.face[i];
    }
    node.face[0]=mark[5];
    node.face[1]=mark[4];
    node.face[2]=mark[2];
    node.face[3]=mark[3];
    node.face[4]=mark[0];
    node.face[5]=mark[1];
}
void turn4(nod& node){
    int i;
    int mark[6];
    for(i=0;i<6;i++){
        mark[i]=node.face[i];
    }
    node.face[0]=mark[4];
    node.face[1]=mark[5];
    node.face[2]=mark[2];
    node.face[3]=mark[3];
    node.face[4]=mark[1];
    node.face[5]=mark[0];
}
bool bfs(){
    int i;
    queue<nod>que;
    que.push(aa1);
    while(!que.empty()){
        nod node;
        node=que.front();
        que.pop();
        if(node.face[0]==aa2.face[0]&&node.face[1]==aa2.face[1]&&node.face[2]==aa2.face[2]&&node.face[3]==aa2.face[3]&&node.face[4]==aa2.face[4]&&node.face[5]==aa2.face[5])
        {
            ans=node.res;
            return 1;
        }
        node.res++;
        for(i=0;i<6;i++){
            num[i]=node.face[i];
        }
        turn1(node);
     //   cout<<"node1"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
        if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
            vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
            que.push(node);

        }

        for(i=0;i<6;i++){
            node.face[i]=num[i];
        }
        turn2(node);
    //    cout<<"node2"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;

        if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
            vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
            que.push(node);
        }


        for(i=0;i<6;i++){
            node.face[i]=num[i];
        }
        turn3(node);
   //     cout<<"node3"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;

        if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
            vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
            que.push(node);
        }

        for(i=0;i<6;i++){
            node.face[i]=num[i];
        }
        turn4(node);
      //  cout<<"node4"<<node.face[0]<<" "<<node.face[1]<<" "<<node.face[2]<<" "<<node.face[3]<<" "<<node.face[4]<<" "<<node.face[5]<<endl;
        if(!vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]){
            vis[node.face[0]][node.face[1]][node.face[2]][node.face[3]][node.face[4]][node.face[5]]=1;
            que.push(node);
        }
    }
    return 0;
}
int main(){
    int i;
    while(cin>>aa1.face[0]){
        ans=0;
        for(i=1;i<6;i++)cin>>aa1.face[i];
        for(i=0;i<6;i++)cin>>aa2.face[i];
        memset(vis,0,sizeof(vis));
        aa1.res=0;
        vis[aa1.face[0]][aa1.face[1]][aa1.face[2]][aa1.face[3]][aa1.face[4]][aa1.face[5]]=1;
        if(bfs())cout<<ans<<endl;
        else cout<<-1<<endl;
    }
    return 0;
}