ZC神最擅长逻辑推理，一日，他给大家讲述起自己儿时的数字玩具。 该玩具酷似魔方，又不是魔方。具体来说，它不是一个3 * 3 * 3的结构，而是4 * 2的结构。 按照该玩具约定的玩法，我们可反复地以如下三种方式对其做变换： A． 交换上下两行。比如，图(a)经此变换后结果如图(b)所示。 B． 循环右移（ZC神从小就懂得这是什么意思的）。比如，图(b)经此变换后结果如图©所示。 C． 中心顺时针旋转。比如，图©经此变换后结果如图(d)所示。 ZC神自小就是这方面的天才，他往往是一只手还没揩干鼻涕，另一只手已经迅速地将处于任意状态的玩具复原至如图(a)所示的初始状态。物质极其匮乏的当年，ZC神只有一个这样的玩具；物质极大丰富的今天，你已拥有多个处于不同状态的玩具。现在，就请将它们全部复原吧。
第一行是一个正整数，即你拥有的魔方玩具总数N。 接下来共N行，每行8个正整数，是1~8的排列，表示该玩具的当前状态。 这里，魔方状态的表示规则为：前四个数自左向右给出魔方的第一行，后四个数自右向左给出第二行。比如，初始状态表示为“1 2 3 4 5 6 7 8”。
共N行，各含一个整数，依次对应于复原各玩具所需执行变换的最少次数。 特别地，若某个玩具不可复原，则相应行输出-1。
对于60%的数据，N = 1 对于100%的数据，1 <= N <= 1,000 时间：1 sec 空间：20MB
状态转换图及其搜索
代码实现
利用BFS搜索通过三种变换可以变成什么状态，并记录下来。对字符串求一个hash值，然后用数组记录可达性。在查询的时候对要查询的字符串求hash值，就可以O(1)O(1)地输出查询结果。
复杂度分析：
时间复杂度： O ( 1 ) O(1) O(1)空间复杂度： O ( n ) O(n) O(n)说明： 下述代码全部为【数据结构与算法实验 OJ 平台】提交过的代码。
#include <cstdio> #include <iostream> #include <math.h> using namespace std; int f[10]; int dists[40320 + 5]; struct Node1 { int data, dataList[10]; int Couter(); void Exchange(int &, int &); void Fun1(); void Fun2(); void Fun3(); } queue[41000]; int Node1::Couter() { data = 0; for (int i = 1, x; i <= 8; i++) { x = 0; for (int j = i + 1; j <= 8; j++) { if (dataList[j] < dataList[i]) { x++; } } data += x * f[9 - i]; } return data; } void bfs() { Node1 current; for (int i = 1; i <= 8; i++) { current.dataList[i] = i; } int head = 0, tail = 0; dists[current.Couter()] = 1; queue[tail++] = current; Node1 temp; while (head != tail) { current = queue[head++]; head %= 40900; temp = current; temp.Fun1(); if (!dists[temp.Couter()]) { queue[tail++] = temp; tail %= 40900; dists[temp.Couter()] = dists[current.data] + 1; } temp = current; temp.Fun2(); if (!dists[temp.Couter()]) { queue[tail++] = temp; tail %= 40900; dists[temp.Couter()] = dists[current.data] + 1; } temp = current; temp.Fun3(); if (!dists[temp.Couter()]) { queue[tail++] = temp; tail %= 40900; dists[temp.Couter()] = dists[current.data] + 1; } } } void init() { f[1] = 0; f[2] = 1; for (int i = 3; i <= 8; i++) { f[i] = f[i - 1] * (i - 1); } } int main() { init(); bfs(); int n; cin >> n; Node1 x; for (int i = 0; i < n; i++) { for (int j = 1; j <= 8; j++) cin >> x.dataList[j]; cout << dists[x.Couter()] - 1 << endl; } return 0; } void Node1::Exchange(int &a, int &b) { int temp; temp = a; a = b; b = temp; } void Node1::Fun1() { for (int i = 1; i <= 4; i++) Exchange(dataList[i], dataList[9 - i]); } void Node1::Fun2() { dataList[0] = dataList[1]; for (int i = 1; i <= 3; i++) { dataList[i] = dataList[i + 1]; } dataList[4] = dataList[0]; dataList[9] = dataList[8]; for (int i = 8; i >= 6; i--) { dataList[i] = dataList[i - 1]; } dataList[5] = dataList[9]; } void Node1::Fun3() { dataList[0] = dataList[2]; dataList[2] = dataList[3]; dataList[3] = dataList[6]; dataList[6] = dataList[7]; dataList[7] = dataList[0]; }