【数据结构与算法实习】题目10 玩具(Toy)

本文主要是介绍【数据结构与算法实习】题目10 玩具(Toy)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：
ZC神最擅长逻辑推理，一日，他给大家讲述起自己儿时的数字玩具。
该玩具酷似魔方，又不是魔方。具体来说，它不是一个3 * 3 * 3的结构，而是4 * 2的结构。

在这里插入图片描述

按照该玩具约定的玩法，我们可反复地以如下三种方式对其做变换：

交换上下两行。比如，图(a)经此变换后结果如图(b)所示。
循环右移（ZC神从小就懂得这是什么意思的）。比如，图(b)经此变换后结果如图©所示。
中心顺时针旋转。比如，图©经此变换后结果如图(d)所示。

ZC神自小就是这方面的天才，他往往是一只手还没揩干鼻涕，另一只手已经迅速地将处于任意状态的玩具复原至如图(a)所示的初始状态。物质极其匮乏的当年，ZC神只有一个这样的玩具；物质极大丰富的今天，你已拥有多个处于不同状态的玩具。现在，就请将它们全部复原吧。

输入格式:
第一行是一个正整数，即你拥有的魔方玩具总数N。
接下来共N行，每行8个正整数，是1~8的排列，表示该玩具的当前状态。
这里，魔方状态的表示规则为：前四个数自左向右给出魔方的第一行，后四个数自右向左给出第二行。比如，初始状态表示为“1 2 3 4 5 6 7 8”。

要求：
1 <= N <= 1,000

输出格式:
共N行，各含一个整数，依次对应于复原各玩具所需执行变换的最少次数。
特别地，若某个玩具不可复原，则相应行输出-1。

输入样例:

2
1 2 3 4 5 6 7 8
8 6 3 5 4 2 7 1

输出样例:

0
2

题解：

//本题的逻辑结构：状态表、队列
//本题的存储结构：顺序
//解题思路和算法：利用康拓展开，将每一种状态标号，将数组对应标号的下标的数据设置为距离目标（12348765）状态还有多少步
//              通过队列进行广度遍历，将从初始状态演变出的所有
//              状态距离目标状态的步数存入数组，输入的数据直接和数组比对，快速得出结果
//效率:对每组数据判断时间复杂度 O(1)、总时间复杂度O(n)、空间复杂度 O(n)：
//测试数据：//输入：2// 1 2 3 4 5 6 7 8// 8 6 3 5 4 2 7 1// 输出：0 2// 输入：3// 1 3 4 5 2 6 8 7// 3 4 8 7 2 1 5 6// 4 8 6 5 3 2 7 1// 输出：16 13 14#include <stdlib.h>
#include <math.h>
#include<stdio.h>
int factorialArr[10];
int Steps[50000];
struct statusNode
{int data;int List[10];int Couter(){//康托展开给每种状况进行排序，如对于 2 4 1 5 3// 第一位是2，比他小的只有1，所以对于这一位比他小的有4！个数// 第二位是4，比他小的有1 2 3，2不考虑，所以有2*3！个数能比他小// 把每位数加起来为36，则排名第37data = 0;for (int i = 1, sNode; i <= 8; i++){sNode = 0;for (int j = i + 1; j <= 8; j++){if (List[j] < List[i]){sNode++;}}data += sNode * factorialArr[9 - i];}return data;}void Trans(int &a, int &b){int tempStatus;tempStatus = a;a = b;b = tempStatus;}void makeTrans(){for (int i = 1; i <= 4; i++)Trans(List[i], List[9 - i]);}void makeCircle(){List[0] = List[1];for (int i = 1; i <= 3; i++){List[i] = List[i + 1];}List[4] = List[0];List[9] = List[8];for (int i = 8; i >= 6; i--){List[i] = List[i - 1];}List[5] = List[9];}void makeChange(){List[0] = List[2];List[2] = List[3];List[3] = List[6];List[6] = List[7];List[7] = List[0];}} Que[50000];void makeFactorialArr()
{ // 获取{8!, 7!, 6!, 5!, 4!, ... }// 在康托展开调用factorialArr[1] = 0;factorialArr[2] = 1;for (int i = 3; i <= 8; i++){factorialArr[i] = factorialArr[i - 1] * (i - 1);}
}void BFS()
{statusNode currStatus;for (int i = 1; i <= 8; i++){currStatus.List[i] = i;}int head = 0, tail = 0;Steps[currStatus.Couter()] = 1;//记录变化后的康托序列的访问Que[tail++] = currStatus;//把当前康托序列入队statusNode tempStatus;while (head != tail)//当序列没有变回时{currStatus = Que[head++];//从队列取出状态tempStatus = currStatus;tempStatus.makeTrans();//交换位置if (!Steps[tempStatus.Couter()])//状态码不存在{Que[tail++] = tempStatus;//把该状态入队Steps[tempStatus.Couter()] = Steps[currStatus.data] + 1;//记录变化后的康托序列的访问,记录的是离目标状态的次数}tempStatus = currStatus;tempStatus.makeCircle();if (!Steps[tempStatus.Couter()]){Que[tail++] = tempStatus;Steps[tempStatus.Couter()] = Steps[currStatus.data] + 1;}tempStatus = currStatus;tempStatus.makeChange();if (!Steps[tempStatus.Couter()]){Que[tail++] = tempStatus;Steps[tempStatus.Couter()] = Steps[currStatus.data] + 1;}}
}int main()
{makeFactorialArr();BFS();int n;scanf("%d", &n);statusNode sNode;for (int i = 0; i < n; i++){for (int j = 1; j <= 8; j++)scanf("%d", &sNode.List[j]); printf("%d", Steps[sNode.Couter()]-1);}return 0;
}