HDU 5012

Dice

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1465    Accepted Submission(s): 749

Input

There are multiple test cases. Please process till EOF. 

For each case, the first line consists of six integers a ₁,a ₂,a ₃,a ₄,a ₅,a ₆, representing the numbers on dice A. 

The second line consists of six integers b ₁,b ₂,b ₃,b ₄,b ₅,b ₆, representing the numbers on dice B.

Output

For each test case, print a line with a number representing the answer. If there’s no way to make two dices exactly the same, output -1.

Sample Input

1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
1 2 5 6 4 3
1 2 3 4 5 6
1 4 2 5 3 6

Sample Output

0 3 -1

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
const int inf=(1<<30);

struct Node
{
    int a,b,c,d,e,f;
    int step;
    friend bool operator < (const Node a,const Node b)
    {
        return a.step>b.step;
    }
};
int arr[8],brr[8];
bool vis[7][7][7][7][7][7];
int bfs(int p,int b,int c,int d,int e,int f)
{
    memset(vis,0,sizeof(vis));
    priority_queue <Node> q;
    Node a;
    a.a=p,a.b=b,a.c=c,a.d=d,a.e=e,a.f=f;
    a.step=0;
    q.push(a);
    vis[a.a][a.b][a.c][a.d][a.e][a.f]=1;
    while(!q.empty())
    {
        Node c=q.top();
        q.pop();
        vis[c.a][c.b][c.c][c.d][c.e][c.f]=1;
        if(c.a==arr[1]&&c.b==arr[2]&&c.c==arr[3]&&c.d==arr[4]&&c.e==arr[5]&&c.f==arr[6])
            return c.step;
        if(c.step>=8)break;
        for(int i=1;i<=4;i++)
        {
            Node b=c;
            if(i==1)
            {
                b.step++;
                b.a=c.d,b.b=c.c;
                b.c=c.a,b.d=c.b;
                if(!vis[b.a][b.b][b.c][b.d][b.e][b.f])
                    q.push(b);
            }
            else if(i==2)
            {
                b.step++;
                b.a=c.c,b.b=c.d;
                b.c=c.b,b.d=c.a;
                if(!vis[b.a][b.b][b.c][b.d][b.e][b.f])
                    q.push(b);
            }
            else if(i==3)
            {
                 b.step++;
                b.a=c.f,b.b=c.e;
                b.e=c.a,b.f=c.b;
                if(!vis[b.a][b.b][b.c][b.d][b.e][b.f])
                    q.push(b);
            }
            else if(i==4)
            {
                b.step++;
                b.a=c.e,b.b=c.f;
                b.e=c.b,b.f=c.a;
                if(!vis[b.a][b.b][b.c][b.d][b.e][b.f])
                    q.push(b);
            }
        }
    }
    return -1;
}
int main()
{
    while(~scanf("%d%d%d%d%d%d",&arr[1],&arr[2],&arr[3],&arr[4],&arr[5],&arr[6]))
    {
        for(int i=1;i<=6;i++)
            scanf("%d",&brr[i]);
        int cnt=bfs(brr[1],brr[2],brr[3],brr[4],brr[5],brr[6]);
        printf("%d\n",cnt);
    }
    return 0;
}