acwing 1107 魔板

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
 
using namespace std ;
map<string,pair<char,string> > pre ;
map<string,int> dist ;
 
int x[10] ; 
string get1(string a){
  //cout << s << endl ; 
  string res = "" ;
  for(int i = 0 ; i < 4 ; i ++) res += a[i+4] ;
  for(int i = 4 ; i < 8 ; i ++) res += a[i-4] ;
  return res ;
}
string get2(string a){
  string res = "" ;
  res += a[3] ; res += a[0] ; res += a[1]; res += a[2] ; 
  res += a[7] ; res += a[4] ; res+= a[5] ; res += a[6] ;
  return res ;
}
string get3(string a){
  string res = "" ;
  res+=a;
  res[1] = a[5];
  res[2] = a[1] ;
  res[5] = a[6] ;
  res[6] = a[2] ;
  return res ;
}
int bfs(string start,string e){
  if(start == e ) return 0 ;
  queue<string> q ;
  q.push(start) ;
  dist[start] = 0 ;
  
  while(!q.empty()){
    string now = q.front() ;
    q.pop() ;
    string s[3] ;
    s[0] = get1(now) ;
    s[1] = get2(now) ;
    s[2] = get3(now) ;
    
    for(int i = 0 ; i < 3 ; i ++){
      if(!dist.count(s[i])){
        dist[s[i]] = dist[now] + 1 ;
        pre[s[i]] = {'A'+i,now} ;
        q.push(s[i]) ;
        if(s[i] == e){
          return dist[e] ;
        }
      }
    }
  }
  
  return -1 ;
}
int main(){
  string start ;
  string e ;
  for(int i = 1 ; i <= 8 ; i ++){
    cin >> x[i] ;
  }
  for(int i = 1 ; i <= 4 ; i ++){
    e += (x[i]+'0') ;
  }
  for(int i = 8 ; i >= 5 ; i --){
    e += (x[i]+'0') ;
  }
  start = "12348765";
  //cout << e << endl << start << endl ;
  int step = bfs(start,e);
  cout << step  << endl;  
  string res ;
  while(start!=e){
    //cout << e << endl ;
    res += pre[e].first ;
    e = pre[e].second ;
  }
  reverse(res.begin(),res.end()) ;
  if(step>0)cout << res << endl ;
}