问题 B: 魔板（USACO3.2.5）

问题 B: 魔板（USACO3.2.5）

题目描述

在成功地发明了魔方之后，拉比克先生发明了它的二维版本，称作魔板。这是一张有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之间），表示目标状态。

输出

输出文件包括一个整数，表示最短操作序列的长度。

样例输入

2 6 8 4 5 7 3 1

样例输出

7

思路：广搜，用map记录每个到达过的状态，直至达到目标状态

代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

map<int,bool>mp;

struct dd{

    int a[10],step;

}s,e;

queue<dd>q;

int k,ek;

void bfs()

{

    while(!q.empty())

    {

        //A操作

        for(int i = 1; i <= 8; i++)

            s.a[i]=q.front().a[9-i];

        //获取当前状态，下同

        k=0;

        for(int i =1; i <= 8; i++)

            k=k*10+s.a[i];

        if(!mp[k])

        {

            //没有到达过这种状态，则推入队列，下同

            mp[k]=true;

            s.step=q.front().step+1;

            q.push(s);

        }

        //B操作

        s.a[1]=q.front().a[4];s.a[2]=q.front().a[1];s.a[3]=q.front().a[2];s.a[4]=q.front().a[3];

        s.a[5]=q.front().a[6];s.a[6]=q.front().a[7];s.a[7]=q.front().a[8];s.a[8]=q.front().a[5];

        k=0;

        for(int i =1; i <= 8; i++)

            k=k*10+s.a[i];

        if(!mp[k])

        {

            mp[k]=true;

            s.step=q.front().step+1;

            q.push(s);

        }

        //C操作

        s.a[1]=q.front().a[1];s.a[2]=q.front().a[7];s.a[3]=q.front().a[2];s.a[4]=q.front().a[4];

        s.a[5]=q.front().a[5];s.a[6]=q.front().a[3];s.a[7]=q.front().a[6];s.a[8]=q.front().a[8];

        k=0;

        for(int i =1; i <= 8; i++)

            k=k*10+s.a[i];

        if(!mp[k])

        {

            mp[k]=true;

            s.step=q.front().step+1;

            q.push(s);

        }

        //判定是否达到目标

        if(mp[ek])

        {

            printf("%d\n",q.front().step+1);

            return;

        }

        q.pop();

    }

    return;

}

int main()

{

    for(int i = 1; i <= 8; i++)

        scanf("%d",&e.a[i]);

    for(int i = 1; i <= 8;i++)

        s.a[i]=i;

    s.step=0;

    q.push(s);

    //起始状态

    k=0;

    for(int i =1; i <= 8; i++)

        k=k*10+s.a[i];

    mp[k]=true;

    //目标状态

    ek=0;

    for(int i =1; i <= 8; i++)

        ek=ek*10+e.a[i];

    //特判，防止目标即起始状态

    if(ek==k)

        cout<<0<<endl;

    else

        bfs();

    return 0;

}