题目描述

There are 2 special dices on the table. On each face of the dice, a distinct number was written. Consider a1.a2,a3,a4,a5,a6 to be numbers written on top face, bottom face, left face, right face, front face and back face of dice A. Similarly, consider b1,b2,b3,b4,b5,b6 to be numbers on specific faces of dice B.

It’s guaranteed that all numbers written on dices are integers no smaller than 1 and no more than 6 while ai ≠ aj and bi ≠ bj for all i ≠ j. Specially, sum of numbers on opposite faces may not be 7.

At the beginning, the two dices may face different(which means there exist some i, ai ≠ bi). Ddy wants to make the two dices look the same from all directions(which means for all i, ai = bi) only by the following four rotation operations.(Please read the picture for more information)

Now Ddy wants to calculate the minimal steps that he has to take to achieve his goal.
http://7xibui.com1.z0.glb.clouddn.com/2015/05/C534-1006-1.jpg

思路

这题看见求最小操作步数应该就是BFS题…

我刚开始是先把四个操作模拟出来,好匹配状态…

然后BFS…

AC代码

/*************************************************************************
    > File Name: 6314_B.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: Wed 27 May 2015 09:18:15 PM CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int DiceA[7];
int DiceB[7]; // A, B两个色子
map<int, bool> Mark; // 记录状态

void rotation(int *destdice, int *dice, int direct) { // 模拟四个操作
    memcpy(destdice+1, dice+1, sizeof(int)*6);
    switch(direct) { 
        case 1: // Left Rotation
            swap(destdice[1], destdice[4]);
            swap(destdice[2], destdice[3]);
            swap(destdice[3], destdice[4]);
            break;
        case 2: // Right Rotation
            swap(destdice[1], destdice[3]);
            swap(destdice[3], destdice[4]);
            swap(destdice[2], destdice[3]);
            break;
        case 3: // Front Rotation
            swap(destdice[1], destdice[6]);
            swap(destdice[2], destdice[5]);
            swap(destdice[5], destdice[6]);
            break;
        case 4: // Back Rotation
            swap(destdice[1], destdice[5]);
            swap(destdice[2], destdice[6]);
            swap(destdice[5], destdice[6]);
            break;
    }
}

bool ok(int *dicea, int *diceb) { 检验两个色子状态是否一样
    for(int i=1; i<=6; ++i)
        if(dicea[i] != diceb[i])
            return false;
    return true;
}

struct Stat{ // 状态
    int dice[7]; // 色子状态
    int step; // 当前步数
    Stat(int *Dice, int s=0) { // 构造函数
        step = s;
        memcpy(dice+1, Dice+1, sizeof(int)*6);
    }
};

int bfs() {
    queue<Stat> que;
    que.push(Stat(DiceA, 0)); // 初始状态入队
    while(que.size()) { // 状态数目不为空
        Stat p = que.front(); // 取出当前状态
        que.pop(); 
        if(ok(p.dice, DiceB)) // 到达最终状态,返回最小步数
            return p.step;
        for(int op=1; op<=4; ++op) { // 四个操作
            Stat next(p.dice, p.step+1); // 下一步
            rotation(next.dice, p.dice, op); // 下一步操作
            int mark = next.dice[1] + 
            next.dice[2]*10 + 
            next.dice[3]*100 + 
            next.dice[4]*1000 + 
            next.dice[5]*10000 +
            next.dice[6]*100000; // 记录下一步色子状态
            if(!Mark.count(mark)) { // 若无该状态,入队
                Mark[mark] = true; // 记录该状态
                que.push(next);
            }
        }
    }
    return -1; // 无法到达最终状态
}

int main()
{
#ifdef Oj
    freopen("6314_B.in", "r", stdin);
#endif
    while(scanf("%d%d%d%d%d%d", &DiceA[1],&DiceA[2],&DiceA[3],&DiceA[4],
    &DiceA[5],&DiceA[6]) == 6 && scanf("%d%d%d%d%d%d", &DiceB[1],&DiceB[2],
    &DiceB[3],&DiceB[4],&DiceB[5],&DiceB[6]) == 6 ) {
        Mark.clear(); // 清除状态标记
        cout << bfs() << endl;
    }
    return 0;
}