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

作者: wjyyy 分类: 搜索,解题报告 发布时间: 2018-08-08 17:11

点击量:16

 

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

 

题目背景

在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */