首页 > 代码库 > BFS [HDU 1430] 魔板

BFS [HDU 1430] 魔板

魔板

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1988    Accepted Submission(s): 407


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
12345678172453681234567882754631
 

 

Sample Output
CAC
 
预处理
#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <string>using namespace std;#define N 326888bool vis[N];string way[N];int fac[]={1,1,2,6,24,120,720,5040,40320,326880};struct node{    string s;    string op;};int Find(string &s)   {    int i,j,res=0;    bool has[10]={0};    for(i=0;i<9;i++)    {        int x=s[i]-0,y=0;        for(j=1;j<x;j++)        {            if(!has[j]) y++;        }        res+=y*fac[8-i];        has[x]=1;    }    return res+1;}void bfs(){    int i,j;    node now,next;    queue<node> q;    memset(vis,0,sizeof(vis));    now.s="12345678";    now.op="";    q.push(now);    vis[Find(now.s)]=1;    while(!q.empty())    {        now=q.front();        q.pop();        way[Find(now.s)]=now.op;        for(int i=1;i<=3;i++)        {            next=now;            if(i==1)            {                next.op+=A;                swap(next.s[0],next.s[7]);                swap(next.s[1],next.s[6]);                swap(next.s[2],next.s[5]);                swap(next.s[3],next.s[4]);            }            else if(i==2)            {                next.op+=B;                char ch=next.s[3];                for(j=3;j>=1;j--) next.s[j]=next.s[j-1];                next.s[0]=ch;                ch=next.s[4];                for(j=4;j<7;j++) next.s[j]=next.s[j+1];                next.s[7]=ch;            }            else            {                next.op+=C;                char ch=next.s[1];                next.s[1]=next.s[6];                next.s[6]=next.s[5];                next.s[5]=next.s[2];                next.s[2]=ch;            }            if(!vis[Find(next.s)])            {                vis[Find(next.s)]=1;                q.push(next);            }        }    }}int main(){    bfs();    string s1,s2;    while(cin>>s1>>s2)    {        map<char,char> mp;        for(int i=0;i<8;i++) //好吧、这儿写反了,WA- -        {            mp[s1[i]]=i+1+0;        }        for(int i=0;i<8;i++)        {            s2[i]=mp[s2[i]];        }        cout<<way[Find(s2)]<<endl;    }    return 0;}

 

BFS [HDU 1430] 魔板