魔板
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2874 Accepted Submission(s): 635
魔方风靡全球之后不久,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
给你魔板的初始状态与目标状态,请给出由初态到目态变换数最少的变换步骤,若有多种变换方案则取字典序最小的那种。
17245368
12345678
82754631
AC
列如:位置:12345678 12345678
起初: 63728145 变 12345678
终点: 86372541 成 51234876
解释一下:初:6在第1个位,那么在终点中找6用1代替,3在第2个位,在终点中找3用2代替,依次类推。
一开始我们就先按 12345678 这样的顺序建立了一棵像树一样的,如果直接从初态不进行转变的话,那么我们的结果可能有很多的走法,有可能是先走A或B都可以到目标,有多条路时,但是先走了B的路径,必须要输出小的也就是从A开始的那条路,那怎么办呢,就可以用转化的思想了,把初始状态变成12345678,这样的话,我们一开始就是从这样的顺序算出来的!!所以必须先进行转换,在从目标往上找并记下路径,一直找到最终父节点:12345678.
这题映射之后直接一次BFS就行了...非常NB。。
///X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! a[i]表示第i个元素的逆序数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
using namespace std;
const int N = ;
int a[],b[];
char str[],str1[];
bool vis[N];
int fab[]={,,,,,,,};
struct Node
{
int val[];
int Hash;
};
struct Way{
char way; ///记录路径
int pre;
}node2[N];
int contor(Node s){
int x= ;
for(int i=;i>=;i--){
int cnt = ;
for(int j=i-;j>=;j--){
if(s.val[i]<s.val[j]) cnt++;
}
x+=cnt*fab[i-];
}
return x;
}
void A(Node &s){
swap(s.val[],s.val[]);
swap(s.val[],s.val[]);
swap(s.val[],s.val[]);
swap(s.val[],s.val[]);
}
void B(Node &s){
swap(s.val[],s.val[]),swap(s.val[],s.val[]),swap(s.val[],s.val[]);
swap(s.val[],s.val[]),swap(s.val[],s.val[]),swap(s.val[],s.val[]);
}
void C(Node &s){
swap(s.val[],s.val[]),swap(s.val[],s.val[]),swap(s.val[],s.val[]);
}
void bfs(Node s)
{
for(int i=;i<N;i++){
node2[i].pre = -;
}
memset(vis,false,sizeof(vis));
queue<Node> q;
node2[s.Hash].pre = -;
vis[s.Hash] = true;
q.push(s);
while(!q.empty()){
Node now = q.front();
q.pop();
Node next;
next = now;
A(next);
int k = contor(next);
if(!vis[k]){
vis[k] = true;
next.Hash = k;
node2[next.Hash].pre = now.Hash;
node2[next.Hash].way = 'A';
q.push(next);
}
next = now;
B(next);
k = contor(next);
if(!vis[k]){
vis[k] = true;
next.Hash = k;
node2[next.Hash].pre = now.Hash;
node2[next.Hash].way = 'B';
q.push(next);
}
next = now;
C(next);
k = contor(next);
if(!vis[k]){
vis[k] = true;
next.Hash = k;
node2[next.Hash].pre = now.Hash;
node2[next.Hash].way = 'C';
q.push(next);
}
}
}
struct Node3{
char c;
int idx;
}node3[];
void dfs(int x){
if(node2[x].pre==-) return;
dfs(node2[x].pre);
printf("%c",node2[x].way);
}
int main()
{
Node s;
for(int i=;i<=;i++){
s.val[i] = i;
}
s.Hash = contor(s);
bfs(s);
while(scanf("%s",str+)!=EOF)
{
scanf("%s",str1+);
for(int i=;i<=;i++){
node3[i].c = str[i];
node3[i].idx = i;
}
Node s;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(str1[i]==node3[j].c){
s.val[i] = node3[j].idx;
break;
}
}
}
int x= contor(s);
dfs(x);
printf("\n");
}
}