A41019. 魔板
填空题
困难
知识点
题目描述
魔板
题目描述
在魔方风靡全球之后不久，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
给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。
输入格式
每组测试数据包括两行，分别代表魔板的初态与目态。
输出格式
对每组测试数据输出满足题意的变换步骤。
样例输入
12345678
17245368
12345678
82754631样例输出
C
AC参考答案
#include<iostream>
#include<cstring>
struct
{
char str[9],opt;
int par;
}queue[40330],tmp,nxt;
int fac[8]={1,1,2,6,24,120,720,5040},vis[40330];
char opt[4]="ABC",aim[9];
void(*fun[3])(char *str);
int hash(char *str)
{
int i,j,cnt,sum=0;
for(i=0;i<8;i++)
{
for(cnt=0,j=i+1;j<8;j++)
if(str[j]>str[i])
cnt++;
sum+=cnt*fac[7-i];
}
if(vis[sum])
return 1;
vis[sum]=1;
return 0;
}
void swap(char *a,char *b)
{
*a+=*b;
*b=*a-*b;
*a-=*b;
return;
}
void optA(char *str)
{
swap(&str[0],&str[4]);
swap(&str[1],&str[5]);
swap(&str[2],&str[6]);
swap(&str[3],&str[7]);
return;
}
void optB(char *str)
{
int i;
char tmp;
for(tmp=str[3],i=3;i>0;i--)
str[i]=str[i-1];
str[0]=tmp;
for(tmp=str[7],i=7;i>4;i--)
str[i]=str[i-1];
str[4]=tmp;
return;
}
void optC(char *str)
{
char tmp=str[1];
str[1]=str[5];
str[5]=str[6];
str[6]=str[2];
str[2]=tmp;
return;
}
void print(int k)
{
if(queue[k].par==-1)
return;
print(queue[k].par);
putchar(queue[k].opt);
return;
}
void bfs()
{
int front=0,rear=0,i;
tmp.opt=0;
tmp.par=-1;
if(!strcmp(tmp.str,aim))
return;
hash(tmp.str);
queue[rear++]=tmp;
while(front!=rear)
{
tmp=queue[front];
for(i=0;i<3;i++)
{
nxt=tmp;
(*fun[i])(nxt.str);
if(hash(nxt.str))
continue;
nxt.opt=opt[i];
nxt.par=front;
queue[rear]=nxt;
if(!strcmp(nxt.str,aim))
{
print(rear);
return;
}
rear++;
}
front++;
}
return;
}
int main()
{
fun[0]=optA;
fun[1]=optB;
fun[2]=optC;
while(scanf("%s",tmp.str)!=EOF)
{
std::cin>>aim;
swap(&tmp.str[4],&tmp.str[7]);
swap(&tmp.str[5],&tmp.str[6]);
swap(&aim[4],&aim[7]);
swap(&aim[5],&aim[6]);
memset(vis,0,sizeof(vis));
bfs();
std::cout<<std::endl;
}
return 0;
}
上一题
下一题