ACM/ICPC 之 BFS(离线)+康拓展开(TSH OJ-玩具(Toy))

时间:2024-01-19 11:57:26

祝大家新年快乐,相信在新的一年里一定有我们自己的梦!

这是一个简化的魔板问题,只需输出步骤即可。

玩具(Toy)


描述

ZC神最擅长逻辑推理,一日,他给大家讲述起自己儿时的数字玩具。

该玩具酷似魔方,又不是魔方。具体来说,它不是一个3 * 3 * 3的结构,而是4 * 2的结构。

ACM/ICPC 之 BFS(离线)+康拓展开(TSH OJ-玩具(Toy))

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

A. 交换上下两行。比如,图(a)经此变换后结果如图(b)所示。

B. 循环右移(ZC神从小就懂得这是什么意思的)。比如,图(b)经此变换后结果如图(c)所示。

C. 中心顺时针旋转。比如,图(c)经此变换后结果如图(d)所示。

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

输入

第一行是一个正整数,即你拥有的魔方玩具总数N。

接下来共N行,每行8个正整数,表示该玩具的当前状态。

这里,魔方状态的表示规则为:前四个数自左向右给出魔方的第一行,后四个数自右向左给出第二行。比如,初始状态表示为“1 2 3 4 5 6 7 8”。

输出

共N行,各含一个整数,依次对应于复原各玩具所需执行变换的最少次数。

特别地,若某个玩具不可复原,则相应行输出-1。

输入样例

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

输出样例

0
2

限制

对于60%的数据,N = 1

对于100%的数据,1 <= N <= 1,000

时间:1 sec

空间:20MB

提示

状态转换图及其搜索


  解法可以参看我的另一篇文章:ACM/ICPC 之 BFS(离线)+康拓展开 (HDU1430-魔板)

  具体代码如下:

 //玩具(Toy),类似魔板问题,但只需输出步骤数即可
//Time:28Ms Memory:13376MB (No.10)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAX 40321
int Map[MAX]; //状态图
int fac[] = { ,,,,,,,};
struct Board{
int fa; //记录上一状态
int val; //Hash值
char str[];
void Contor();
}m[*MAX],ts;
void Board::Contor()
{
int num = ;
for (int i = ; i < ; i++)
{
int tmp = ;
for (int j = i + ; j < ; j++)
{
if (this->str[j] < this->str[i]) tmp++;
}
num += tmp*fac[ - i];
}
this->val = num;
}
void Init(char s[])
{
int rear = ;
int tail = ;
strcpy(m[].str, s);
m[].Contor();
while (rear < tail) {
if (Map[m[rear].val])
{
rear++;
continue;
}
Map[m[rear].val] = Map[m[m[rear].fa].val] + ;
/*由于是反向搜索,因此将逆向操作即可*/
// 交换行
for (int i = ; i < ; i++)
m[tail].str[(i + ) % ] = m[rear].str[i];
m[tail].Contor();
if (!Map[m[tail].val]) {
m[tail].fa = rear;
tail++;
}
// 循环左移
for (int i = ; i < ; i++)
m[tail].str[(i + ) % ] = m[rear].str[i];
for (int i = ; i < ; i++)
m[tail].str[(i + ) % + ] = m[rear].str[i];
m[tail].Contor();
if (!Map[m[tail].val]) {
m[tail].fa = rear;
tail++;
}
// 中心逆旋转
strcpy(m[tail].str, m[rear].str);
m[tail].str[] = m[rear].str[]; m[tail].str[] = m[rear].str[];
m[tail].str[] = m[rear].str[]; m[tail].str[] = m[rear].str[];
m[tail].Contor();
if (!Map[m[tail].val]) {
m[tail].fa = rear;
tail++;
}
rear++;
}
}
int main()
{
/*预处理*/
Init("");
int T;
scanf("%d", &T);
while (T--)
{
int tmp;
for (int i = ; i < ; i++)
{
scanf("%d", &tmp);
ts.str[i] = tmp + '';
}
for (int i = ; i < ; i++)
{
scanf("%d", &tmp);
ts.str[( - i) + ] = tmp + '';
}
ts.Contor();
printf("%d\n", Map[ts.val] - );
}
return ;
}