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

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

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

 

玩具(Toy)

---

描述

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

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

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

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[8] = { 1,1,2,6,24,120,720,5040};
struct Board{
    int fa;        //记录上一状态
    int val;    //Hash值
    char str[9];
    void Contor();
}m[2*MAX],ts;
void Board::Contor()
{
    int num = 0;
    for (int i = 0; i < 8; i++)
    {
        int tmp = 0;
        for (int j = i + 1; j < 8; j++)
        {
            if (this->str[j] < this->str[i]) tmp++;
        }
        num += tmp*fac[7 - i];
    }
    this->val = num;
}
void Init(char s[9])
{
    int rear = 0;
    int tail = 1;
    strcpy(m[0].str, s);
    m[0].Contor();
    while (rear < tail) {
        if (Map[m[rear].val])
        {
            rear++;
            continue;
        }
        Map[m[rear].val] = Map[m[m[rear].fa].val] + 1;
        /*由于是反向搜索，因此将逆向操作即可*/
        // 交换行
        for (int i = 0; i < 8; i++)
            m[tail].str[(i + 4) % 8] = m[rear].str[i];
        m[tail].Contor();
        if (!Map[m[tail].val]) {
            m[tail].fa = rear;
            tail++;
        }
        // 循环左移
        for (int i = 0; i < 4; i++)
            m[tail].str[(i + 3) % 4] = m[rear].str[i];
        for (int i = 4; i < 8; i++)
            m[tail].str[(i + 3) % 4 + 4] = 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[5] = m[rear].str[1]; m[tail].str[1] = m[rear].str[2];
        m[tail].str[2] = m[rear].str[6]; m[tail].str[6] = m[rear].str[5];
        m[tail].Contor();
        if (!Map[m[tail].val]) {
            m[tail].fa = rear;
            tail++;
        }
        rear++;
    }
}
int main()
{
    /*预处理*/
    Init("12348765");
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int tmp;
        for (int i = 0; i < 4; i++)
        {
            scanf("%d", &tmp);
            ts.str[i] = tmp + '0';
        }
        for (int i = 4; i < 8; i++)
        {
            scanf("%d", &tmp);
            ts.str[(8 - i) + 3] = tmp + '0';
        }
        ts.Contor();
        printf("%d\n", Map[ts.val] - 1);
    }
    return 0;
}