题目描述
https://www.acwing.com/problem/content/1109/
输入样例
2 6 8 4 5 7 3 1
输出样例
7
BCABCCB
bfs广度优先搜索
C++ 代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<int,bool> mp;
struct dd{
int a[10],step;
string ans;
}s,e;
queue<dd>q;
int k,ek;
void bfs(){
while(!q.empty()){
//A
for(int i=1;i<=8;i++)
s.a[i]=q.front().a[9-i];
k=0;
for(int i=1;i<=8;i++)
k=k*10+s.a[i];
if(!mp[k]){
mp[k]=true;
s.step=q.front().step+1; s.ans = q.front().ans + 'A';
q.push(s);
}
if(mp[ek]){
printf("%d\n",q.front().step + 1);
cout << s.ans << '\n';
return;
}
//B
s.a[1]=q.front().a[4];s.a[2]=q.front().a[1];s.a[3]=q.front().a[2];s.a[4]=q.front().a[3];
s.a[5]=q.front().a[6];s.a[6]=q.front().a[7];s.a[7]=q.front().a[8];s.a[8]=q.front().a[5];
k=0;
for(int i=1;i<=8;i++)
k=k*10+s.a[i];
if(!mp[k]){
mp[k]=true;
s.step=q.front().step+1; s.ans = q.front().ans + 'B';
q.push(s);
}
if(mp[ek]){
printf("%d\n",q.front().step + 1);
cout << s.ans << '\n';
return;
}
//C
s.a[1]=q.front().a[1];s.a[2]=q.front().a[7];s.a[3]=q.front().a[2];s.a[4]=q.front().a[4];
s.a[5]=q.front().a[5];s.a[6]=q.front().a[3];s.a[7]=q.front().a[6];s.a[8]=q.front().a[8];
k=0;
for(int i=1;i<=8;i++)
k=k*10+s.a[i];
if(!mp[k]){
mp[k]=true;
s.step=q.front().step+1; s.ans = q.front().ans + 'C';
q.push(s);
}
if(mp[ek]){
printf("%d\n",q.front().step + 1);
cout << s.ans << '\n';
return;
}
q.pop();
}
return;
}
int main(){
for(int i=1;i<=8;i++)
scanf("%d",&e.a[i]);
for(int i=1;i<=8;i++)
s.a[i]=i;
s.step=0; s.ans = "";
q.push(s);
//起始状态
k=0;
for(int i=1;i<=8;i++)
k=k*10+s.a[i];
mp[k]=true;
//目标状态
ek=0;
for(int i=1;i<=8;i++)
ek=ek*10+e.a[i];
//特判
if(ek==k)
cout<<0<<endl;
else
bfs();
return 0;
}