作为菜鸟 直接暴力

队列：存储图的状态string

哈希表：
键：到达的状态
值：到达该状态需要的步数；到达该状态需要的操作序列

这里用了unordered_map测试下比map快了一倍多

C++ 代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;
typedef pair<int,string> PIS;
char op[4]={'A','B','C'};
queue<string> q;
unordered_map<string,PIS> HASH;
void update(string temp,int step,string xu){
    if(!HASH.count(temp)){
        HASH[temp]={step,xu};
        q.push(temp);
    }
    // else
    // HASH[temp].second=(xu>HASH[temp].second)?xu:HASH[temp].second;
    // step不需要比较大小，因为第一次搜到的一定需要的最小步数
    // 加上其实没啥作用，枚举的顺序已经决定是字典序
}
string to_change(string temp,int i){
    if(!i) reverse(temp.begin(),temp.end());
    if(i==1) temp=temp[3]+temp.substr(0,3)+temp.substr(5,3)+temp[4];
    if(i==2){
        char c=temp[1];temp[1]=temp[6];temp[6]=temp[5];temp[5]=temp[2];temp[2]=c;
    }
    return temp;
}
PIS bfs(string end){
    string start="12345678";
    q.push(start);
    HASH[start].first=0;
    while(q.size()){
        string cur=q.front();q.pop();
        int step=HASH[cur].first;
        string xu=HASH[cur].second;
        if(cur==end)return HASH[cur];//包括了一开始end==start，返回结点的二维为空
        for(int i=0;i<3;i++){
            string temp=cur;
            temp=to_change(temp,i);//三种改变
            update(temp,step+1,xu+op[i]);//去更新哈希和队列
        }
    }
}
int main(){
    string end;
    int c;
    for(int i=0;i<8;i++){
        scanf("%d",&c);
        end+=c+'0';
    }
    PIS res=bfs(end);
    cout<<res.first<<endl<<res.second;
    return 0;   
}

当然哈希表的值可以不是结构体，只需要记录序列即可，想怎么写就怎么写

char op[4]={'A','B','C'};
queue<string> q;
unordered_map<string,string> HASH;
void update(string temp,string xu){
    if(!HASH.count(temp)){
        HASH[temp]=xu;
        q.push(temp);
    }
}
string to_change(string temp,int i){
    if(!i) reverse(temp.begin(),temp.end());
    if(i==1) temp=temp[3]+temp.substr(0,3)+temp.substr(5,3)+temp[4];
    if(i==2){
        char c=temp[1];temp[1]=temp[6];temp[6]=temp[5];temp[5]=temp[2];temp[2]=c;
    }
    return temp;
}
string bfs(string end){
    string start="12345678";
    q.push(start);
    while(q.size()){
        string cur=q.front();q.pop();
        string xu=HASH[cur];
        if(cur==end)return HASH[cur];//包括了一开始end==start，返回结点的二维为空
        for(int i=0;i<3;i++){
            string temp=cur;
            temp=to_change(temp,i);
            update(temp,xu+op[i]);
        }
    }
}
int main(){
    string end;
    int c;
    for(int i=0;i<8;i++){
        scanf("%d",&c);
        end+=c+'0';
    }
    string res=bfs(end);
    cout<<res.size()<<endl;
    if(res.size())
    cout<<res;
    return 0;   
}