[原创]HDU 1430 魔板 [BFS+康拓展开]【数学】
[原创]HDU 1430 魔板 [BFS+ 康拓展开]【数学】
2016-11-05 16:48:35 Tabris_ 阅读数：574
博客爬取于 2020-06-14 22:42:50
以下为正文
版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53046282
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1430
---------------------------------------------.
魔板
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2968 Accepted Submission(s): 672
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
Author
LL
---------------------------------------------.
题目大意 ：中文题 自己读。。。。
解题思路：
首先可以明确的是 这个字符串改变之前和改变之后的关系是一定有的 那么原串和终串无论是什么 只要讲原串和终串映射回“12345678”这样的话 就能够计算了
那样的话 所有的解都可以变成 “12345678” 这个串的变化 ；
由于 8！=40320 状态数目非常少 变化也只有三种 那么我们只要用 BFS 就可以了 利用广度优先的特性 求出的解也是最优的
那么首先 BFS 预处理结果一下就行了 串的变化模拟就可以了
后来计算的时候 把原串和终串处理一下 变成"12345678"与"balabala"的样子 然后输出结果就行了
但是在标记的时候 想到用康托展开的值来标记 而不是用 map 映射（但是想想 map 映射 也没什么毛病吧）。
这个代码确实是 AC 的 只是 win7 CB13.2 运行会渣掉 找了 1 天 BUG 还是没有找到 最后提交上去想保存一下代码的时候 发现居然 AC 了!! AC 了！
附本题代码
----------------------------.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| # include <bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) ((a)>0?(a):-(a))
# define min(a,b) ((a)>(b)?(a):(b))
# define lalal puts("*******")
typedef long long int LL ;
typedef unsigned long long int LLu ;
/*******************************/
bool vis[40050];
int jiecheng[10]={1,1,2,6,24,120,720,5040,40320,362880};
int Cantor_expansion(string &a){
int x=0,tem=0;
for(int i=0;i<8;i++){
tem = 0;
for(int j=i+1;j<8;j++)
if(a[j]<a[i]) tem++;
x+=tem*jiecheng[7-i];
}
return x;
}
void op_A(string &a){
for(int i=0;i<4;i++) swap(a[i],a[7-i]);
}
void op_B(string &a){
char t=a[0];
for(int i=1;i<4;i++) swap(t,a[i]);
a[0]=t;
t=a[7];
for(int i=7;i>=4;i--) swap(t,a[i]);
a[7]=t;
}
void op_C(string &a){
swap(a[1],a[2]);
swap(a[1],a[5]);
swap(a[1],a[6]);
}
struct node {
string str,step;
int x;
};
string mmp[44444];
void BFS(){
memset(vis,false,sizeof(vis));
queue<node >q;
string a="12345678";
int x=Cantor_expansion(a);
vis[x]=1;
mmp[x]="";
node tem ,tmp;
tem.str=a;
tem.step="";
tem.x=x;
q.push(tem);
while(!q.empty()){
tmp=q.front();q.pop();
//AAAAAAAAAAAAA
tem=tmp;
op_A(tem.str);
tem.x=Cantor_expansion(tem.str);
if(!vis[tem.x]){
vis[tem.x]=true;
tem.step+="A";
mmp[tem.x]=tem.step;
q.push(tem);
}
//BBBBBBBBBBBBB
tem=tmp;
op_B(tem.str);
tem.x=Cantor_expansion(tem.str);
if(!vis[tem.x]){
vis[tem.x]=true;
tem.step+="B";
mmp[tem.x]=tem.step;
q.push(tem);
}
//CCCCCCCCCCCCC
tem=tmp;
op_C(tem.str);
tem.x=Cantor_expansion(tem.str);
if(!vis[tem.x]){
vis[tem.x]=true;
tem.step+="C";
mmp[tem.x]=tem.step;
q.push(tem);
}
}
return ;
}
void change(string &a,string &b){
map<char,char>mp;
for(int i=0;i<a.size();i++)
mp[a[i]]='1'+i;
for(int i=0;i<b.size();i++)
b[i]=mp[b[i]];
return ;
}
int main(){
BFS();
string a1,b1;
while(cin>>a1>>b1){
change(a1,b1);
int x=Cantor_expansion(b1);
cout<<mmp[x]<<endl;
}
return 0;
}
|
----------------------------.
