洛谷 P2730 魔板 题解【搜索】【枚举】

点击量：187

    广搜还是比迭代加深厉害啊

目录

题目背景

在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板：

1	2	3	4
8	7	6	5

题目描述

我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8）来表示。这是基本状态。

 

这里提供三种基本操作，分别用大写字母“A”，“B”，“C”来表示（可以通过这些操作改变魔板的状态）：

 

“A”：交换上下两行；

 

“B”：将最右边的一列插入最左边；

 

“C”：魔板中央四格作顺时针旋转。

 

下面是对基本状态进行操作的示范：

A:

8	7	6	5
1	2	3	4

 

B:

4	1	2	3
5	8	7	6

 

 

C:

1	7	2	4
8	6	3	5

 

对于每种可能的状态，这三种基本操作都可以使用。

 

你要编程计算用最少的基本操作完成基本状态到目标状态的转换，输出基本操作序列。

 

输入输出格式

输入格式：

只有一行，包括8个整数，用空格分开（这些整数在范围1~8之间）不换行，表示目标状态。

 

输出格式：

Line 1: 包括一个整数，表示最短操作序列的长度。

 

Line 2: 在字典序中最早出现的操作序列，用字符串表示，除最后一行外，每行输出60个字符。

 

输入输出样例

magic.in	magic.out
2 6 8 4 5 7 3 1	7 BCABCCB

题解：

    一开始用的是迭代加深，不停TLE，发现广搜可以重复性（最优解）剪枝而深搜不行。改成广搜真的跑得特快。。

    因为三种变化都是固定方式的，所以我们可以写3个函数，把当前状态下的魔板给变换一下。然后跑三个方向的广搜，如果下一步状态被用过就把这个枝剪掉。因为8!只有四万多，所以存状态可以用康托展开映射到一个8!大小的表中，或者直接映射到一个八维数组里。而$ 8^8$是一千万，开bool数组是不会爆空间的。实际上为了优化常数，不用0号位置，就要用到$ 9^8$的空间。不过因为这是一个排列，定下了前7位，第八位就确定了，所以可以优化到$ 9^7$。

    通过这种操作，每种状态只进队一次。我们用一个结构体存下这个长为8的数组，把函数封装在结构体里，每次用函数扩展一步就可以了。记录状态不仅要记录方案，而且要记录自己上一步从队列里的哪一个转移过来，这样才能把所有状态给全部找到。

    然而还是不知道什么时候用迭代加深什么时候用广搜。。。

Code：

#include<cstdio>
#include<cstring>
bool used[9][9][9][9][9][9][9][9];
int goal[10];
struct statu
{
    int now[10];
    int from,step;
    void A()
    {
        for(int i=1;i<=4;i++)
        {
            int t=now[i];
            now[i]=now[9-i];
            now[9-i]=t;
        }
    }
    void B()
    {
        int t=now[4];
        for(int i=4;i>=2;i--)
            now[i]=now[i-1];
        now[1]=t;
        t=now[5];
        for(int i=5;i<=7;i++)
            now[i]=now[i+1];
        now[8]=t;
    }
    void C()
    {
        int t=now[2];
        now[2]=now[7];
        now[7]=now[6];
        now[6]=now[3];
        now[3]=t;
    }
    bool check()
    {
        for(int i=1;i<=8;i++)
            if(now[i]!=goal[i])
                return false;
        return true;
    }
    bool ava()//查询是否被用过同时赋值
    {
        bool rm=!used[now[1]][now[2]][now[3]][now[4]][now[5]][now[6]][now[7]][now[8]];
        used[now[1]][now[2]][now[3]][now[4]][now[5]][now[6]][now[7]][now[8]]=1;
        return rm;
    }
}q[100000];
int s[100000],top=0;
int l=0,r=0;
int main()
{
    statu st;
    st.from=-1;
    for(int i=1;i<=8;i++)
        st.now[i]=i;
    for(int i=1;i<=8;i++)
        scanf("%d",&goal[i]);
    if(st.check())
    {
        puts("0");
        return 0;
    }
    used[1][2][3][4][5][6][7][8]=1;
    q[++r]=st;
    int ans;
    while(l<r)
    {
        st=q[++l];
        statu p=st;
        p.A();
        if(p.ava())
        {
            p.from=l;
            p.step=0;
            q[++r]=p;
            if(p.check())
            {
                ans=r;
                break;
            }
        }
        p=st;
        p.B();
        if(p.ava())
        {
            p.from=l;
            p.step=1;
            q[++r]=p;
            if(p.check())
            {
                ans=r;
                break;
            }
        }
        p=st;
        p.C();
        if(p.ava())
        {
            p.from=l;
            p.step=2;
            q[++r]=p;
            if(p.check())
            {
                ans=r;
                break;
            }
        }
    }
    while(~q[ans].from)
    {
        s[++top]=q[ans].step;
        ans=q[ans].from;
    }
    printf("%d\n",top);
    int cnt=0;
    for(int i=top;i;--i)
    {
        printf("%c",s[i]+'A');
        ++cnt;
        if(cnt%60==0)//题目中好像没有这样的数据……
            puts("");
    }
    return 0;
}