题目描述
其实输出操作序列可以简单一些
用一个map存一下转移到当前状态的操作序列,在最后输出的时候直接输出目标状态的操作序列
#include<bits/stdc++.h>
using namespace std;
typedef string str;
str goal="12345678";
str p;
map<str,int> dis;//转移到当前状态所用最少步
map<str,str> ctr;//转移到当前状态的操作序列
inline char what(int x){return x==1?'A':x==2?'B':'C';}//当前状态是由上个状态的那个操作转移过来的
inline str get_A(str x) //A操作
{
str res=x;
swap(res[0],res[7]);
swap(res[1],res[6]);
swap(res[2],res[5]);
swap(res[3],res[4]);
return res;
}
inline str get_B(str x) //B操作
{
str res;
str a(x,0,3),b(x,5,3);
res=x[3]+a+b+x[4];
return res;
}
inline str get_C(str x) //C操作
{
str res=x;
swap(res[2],res[1]);
swap(res[1],res[6]);
swap(res[6],res[5]);
return res;
}
inline int bfs()
{
queue<str> q;
q.push(goal);
dis[p]=0;
str x[4];
while(q.size()){
str now=q.front();
if(now==p){//到达目标状态直接输出
cout<<dis[now]<<"\n";
if(dis[now])
cout<<ctr[now]<<"\n";
exit(0);
}
q.pop();
x[1]=get_A(now);
x[2]=get_B(now);
x[3]=get_C(now);
for(int i=1;i<=3;i++){
if(!dis[x[i]]){
dis[x[i]]=dis[now]+1;
ctr[x[i]]=ctr[now]+what(i);
q.push(x[i]);
}
}
}
}
int main()
{
char ch;
for(int i=1;i<=8;i++)
scanf(" %c",&ch),p+=ch;
bfs();
return 0;
}