题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1430
思路：由于只是8种颜色，所以标号就无所谓了，对起始状态重新修改标号为 12345678，对目标状态标号做相应的修改，先预处理出12345678到所有状态的路径，记录所有状态的pre值，直接输出即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std; struct Node{
char str[];
Node(){};
Node(char _str[]){
for(int i=;i<;i++){
str[i]=_str[i];
}
}
}; int fac[]={,,,,,,,,};
int Get_Hash(Node &p)
{
int val=;
for(int i=;i<;i++){
int cnt=;
for(int j=;j<i;j++){
if(p.str[j]>p.str[i])cnt++;
}
val+=cnt*fac[i];
}
return val;
} void Move_A(Node &p)
{
reverse(p.str,p.str+);
} void Move_B(Node &p)
{
char ch=p.str[];
for(int i=;i>=;i--)p.str[i]=p.str[i-];
p.str[]=ch;
ch=p.str[];
for(int i=;i<=;i++)p.str[i]=p.str[i+];
p.str[]=ch;
} void Move_C(Node &p)
{
swap(p.str[],p.str[]);
swap(p.str[],p.str[]);
swap(p.str[],p.str[]);
} int pre[],ans[];
bool mark[]; void BFS()
{
queue<Node>que;
que.push(Node(""));
memset(mark,false,sizeof(mark));
mark[]=true;
while(!que.empty()){
Node p=que.front();
que.pop();
int p_val=Get_Hash(p);
Node q(p);
Move_A(q);
int q_val=Get_Hash(q);
if(!mark[q_val]){
mark[q_val]=true;
pre[q_val]=p_val;
ans[q_val]='A';
que.push(q);
}
q=p;
Move_B(q);
q_val=Get_Hash(q);
if(!mark[q_val]){
mark[q_val]=true;
pre[q_val]=p_val;
ans[q_val]='B';
que.push(q);
}
q=p;
Move_C(q);
q_val=Get_Hash(q);
if(!mark[q_val]){
mark[q_val]=true;
pre[q_val]=p_val;
ans[q_val]='C';
que.push(q);
}
}
} char S[],T[];
int SS[];
int main()
{
BFS();
while(~scanf("%s%s",S,T)){
for(int i=;i<;i++)SS[S[i]-'']=i;
for(int i=;i<;i++)T[i]=SS[T[i]-'']+'';
Node p=Node(T);
int val=Get_Hash(p);
string ss="";
while(val){
ss+=ans[val];
val=pre[val];
}
reverse(ss.begin(),ss.end());
cout<<ss<<endl;
}
return ;
}
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3567
思路：因为这题有一个特殊的点X，所以枚举X的位置，打出9张前驱表，用魔板题一样的方法将两个状态的对应标号转化，输出就好了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
using namespace std; struct Node{
int map[][];
int x,y;
Node(){}
Node(char *str){
for(int i=,xx=,yy=;str[i];i++){
map[xx][yy]=str[i];
if(str[i]=='X'){ x=xx,y=yy; }
yy++;
if(yy==)xx++,yy=;
}
}
}S; int fac[]= {,,,,,,,,};
//康拓展开
int Get_Hash(Node &p)
{
char str[];
int val=;
for(int i=;i<;i++){
for(int j=;j<;j++){
str[i*+j]=p.map[i][j];
int cnt=;
for(int k=i*+j-;k>=;k--){
if(str[k]>str[i*+j])cnt++;
}
val+=fac[i*+j]*cnt;
}
}
return val;
} int dir[][]={{,},{,-},{,},{-,}};
char Dir[]="dlru";
int pre[][];
char ans[][];
bool mark[]; void bfs(int x)
{
memset(pre[x],-,sizeof(pre[x]));
memset(mark,false,sizeof(mark));
queue<Node>que;
que.push(S);
mark[Get_Hash(S)]=true;
while(!que.empty()){
Node p=que.front();
que.pop();
int p_val=Get_Hash(p);
for(int i=;i<;i++){
Node q=p;
q.x=p.x+dir[i][],q.y=p.y+dir[i][];
if(q.x<||q.x>=||q.y<||q.y>=)continue;
q.map[p.x][p.y]=q.map[q.x][q.y];
q.map[q.x][q.y]='X';
int q_val=Get_Hash(q);
if(mark[q_val])continue;
mark[q_val]=true;
pre[x][q_val]=p_val;
ans[x][q_val]=Dir[i];
que.push(q);
}
}
} char str[];
int num[];
int main()
{
S=Node("X12345678");
bfs();
S=Node("1X2345678");
bfs();
S=Node("12X345678");
bfs();
S=Node("123X45678");
bfs();
S=Node("1234X5678");
bfs();
S=Node("12345X678");
bfs();
S=Node("123456X78");
bfs();
S=Node("1234567X8");
bfs();
S=Node("12345678X");
bfs(); int _case,p,t=;
scanf("%d",&_case);
while(_case --){
scanf("%s", str);
for(int i = , j = ; i <= ; i ++ ){
if(str[i] != 'X') num[str[i] - ''] = j ++;
else p = i;
}
scanf("%s", str);
for(int i=;i<=;i++){
if(str[i]=='X')continue;
str[i]=num[str[i]-'']+'';
}
S=Node(str);
int val=Get_Hash(S);
string ss="";
while(val!=-){
ss+=ans[p][val];
val=pre[p][val];
}
reverse(ss.begin(), ss.end());
printf("Case %d: %d\n",t++,ss.size()-);
for(int i=;i<ss.size();i++)cout<<ss[i];
cout<<endl;
}
return ;
}