2014 网选 5012 Dice(bfs模板)

/*
    题意：就是给定两个筛子，每个筛子上6个面，每个面的数字属于[1,6]， 且互不相同！
    问a筛子最少经过按照题目规定的要求转动，达到和b筛子上下左右前后的数字相同！

    思路：很直白的bfs，将每一种状态对应一个数字，保证这种状态不会重新加入队列中！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int a[7], ss;
int vis[654330];

struct node{
    int k[7];
    node(){}
    node(int a1, int a2, int a3, int a4, int a5, int a6){
        k[1]=a1;
        k[2]=a2;
        k[3]=a3;
        k[4]=a4;
        k[5]=a5;
        k[6]=a6;
    }
    int step;
};

queue<node>q; 

int sum(node x){
    int s=0;
    for(int i=1; i<=6; ++i)
       s= s*10 + x.k[i];
    return s;
}

bool bfs(){
    while(!q.empty()) q.pop();
    node cur(a[1], a[2], a[3], a[4], a[5], a[6]);
    cur.step=0;
    q.push(cur);
    vis[sum(cur)]=1;
    while(!q.empty()){
        cur = q.front();
        if(sum(cur)==ss){
            printf("%d\n", cur.step);
            return true;
        }
        q.pop();
        node *nt = new node(cur.k[5], cur.k[6], cur.k[3], cur.k[4], cur.k[2], cur.k[1]);
        int v = sum(*nt);
        if(!vis[v]){
            vis[v]=1;
            nt->step = cur.step + 1;
            q.push(*nt);
        }

        nt = new node(cur.k[6], cur.k[5], cur.k[3], cur.k[4], cur.k[1], cur.k[2]);
        v = sum(*nt);
        if(!vis[v]){
            vis[v]=1;
            nt->step = cur.step + 1;
            q.push(*nt);
        }

        nt = new node(cur.k[3], cur.k[4], cur.k[2], cur.k[1], cur.k[5], cur.k[6]);
        v = sum(*nt);
        if(!vis[v]){
            vis[v]=1;
            nt->step = cur.step + 1;
            q.push(*nt);
        }

        nt = new node(cur.k[4], cur.k[3], cur.k[1], cur.k[2], cur.k[5], cur.k[6]);
        v = sum(*nt);
        if(!vis[v]){
            vis[v]=1;
            nt->step = cur.step + 1;
            q.push(*nt);
        }
    }
    return false;
}

int main(){
    while(scanf("%d%d%d%d%d%d", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6])!=EOF){
        ss=0;
        for(int i=1; i<=6; ++i){
            int x;
            scanf("%d", &x);
            ss = ss * 10 + x;
        }
        memset(vis, 0, sizeof(vis));
        if(!bfs())
            printf("-1\n");
    }
    return 0;
}