HDU 1430 魔板(BFS+HASH+置换)

HDU 1430 魔板(BFS+HASH+置换)

http://acm.hdu.edu.cn/showproblem.php?pid=1430

Problem Description

在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：

1 2 3 4

8 7 6 5

对于魔板，可施加三种不同的操作，具体操作方法如下：

A: 上下两行互换,如上图可变换为状态87654321

B: 每行同时循环右移一格,如上图可变换为41236785

C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

Input

每组测试数据包括两行，分别代表魔板的初态与目态。

Output

对每组测试数据输出满足题意的变换步骤。

Sample Input

12345678

17245368

12345678

82754631

Sample Output

C

AC

分析:其实本题就是普通的BFS题目不过要用到HASH,这里还有一个关键点就是相对状态.

首先依然是用一个int来表示一个状态,其中st的每三位二进制值表示一个0-7的数.然后用HASH判重,且用到了置换的技巧(简化了代码,具体看源代码.当然不用置换数组op也行)

我们用BFS预处理求出了从初态01234567到任意状态的方案.但是题目假设给了我们初态:32107654 目态:01236547 .我们如何求呢?

我们只需要把32107654看成是01234567(或abcdefgh),然后转换出目态即可.

即:因为目态(01236547)的0在初态的第4个位置上,本来原始状态01234567中.第4个位置上的是3,所以目态的0应该变成3.依此类推.

最终目态code就会被看成是32105674.

网上还有将状态用康托展开编号的,其实并不需要这么麻烦.

AC代码:15ms

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int HASH=100007;
int op[3][8]=
{
    {7,6,5,4,3,2,1,0},
    {3,0,1,2,5,6,7,4},
    {0,6,1,3,4,2,5,7}
};
struct HASHMAP
{
    int head[HASH],next[HASH],st[HASH],size;
    void init()
    {
        size=0;
        memset(head,-1,sizeof(head));
    }
    int find(int _st)
    {
        int h=_st%HASH, u;
        for(u=head[h];u!=-1;u=next[u])
            if(st[u]==_st) break;
        return u;
    }
    void insert(int _st)
    {
        int h=_st%HASH;
        st[size]=_st;
        next[size]=head[h];
        head[h]=size++;
    }
}hm;
int list[HASH],Q[HASH],code[8],pre[HASH];
void decode(int st)
{
    for(int i=7;i>=0;i--) code[i]=st&7, st>>=3;  //错误, 之前写成code[i]=st|7
}
int encode(int *code)
{
    int st=0;
    for(int i=0;i<8;i++) st= (st<<3)|code[i];
    return st;
}
void BFS()
{
    int front=0,tail=1;
    for(int i=0;i<8;i++) code[i]=i;
    int st=encode(code);
    pre[0]=-1; Q[0]=st;
    hm.init(); hm.insert(st);                            //错误,之前hm未初始化
    while(front<tail)
    {
        st=Q[front];
        decode(st);
        for(int d=0;d<3;d++) //3种操作
        {
            int new_code[8];
            for(int i=0;i<8;i++) new_code[i]=code[op[d][i]];
            st=encode(new_code);
            if(hm.find(st)==-1) //注意:这里Q队列和hm中的st状态下标是一一对应的
            {
                hm.insert(st);
                list[tail]=d;
                pre[tail]=front;
                Q[tail++]=st;
            }
        }
        front++;
    }
}
void print(int pos)
{
    if(pre[pos]>=0)             //错误,之前写成pos>=0
    {
        print(pre[pos]);
        printf("%c",list[pos]+'A');
    }
}
int main()
{
    BFS();
    char a[10],b[10];
    while(scanf("%s%s",a,b)==2)
    {
        int tran[10];
        for(int i=0;i<8;i++) tran[a[i]-'1']=i;
        for(int i=0;i<8;i++) code[i]=tran[b[i]-'1'];
        int st=encode(code);
        int pos=hm.find(st);
        print(pos);
        printf("\n");
    }
    return 0;
}