参数解释：
node：记录字符串以及当前次数
A，B：记录原始AB的位置
qu（queue）：bfs使用队列
st（set）：查重，出现过的字符串
is1，is2：用来判断是否交换位置
vt数组：类似于dfs中的x[1,0,-1,0]，用来记录接下来能走的格子，可以不用判断边界条件。

总的是很经典的BFS，但是需要些优化。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
const int INF=1e16;

string s1,s2;

struct node{
    string s;
    int cnt;
};
vector<vector<int>> vt;
int A,B;

void bfs(string s1,string s2){
    queue<node> qu;
    set<string> st;
    string s=s1+s2;
    node no;
    no.s=s;no.cnt=0;
    qu.push(no);
    st.insert(s);
    while(!qu.empty()){
        node no1=qu.front();
        qu.pop();
        string ss=no1.s;

        //cout << ss << " " << no1.cnt << "\n";
        /*
        cout << ss[0] << ss[1] << ss[2] << "\n";
        cout << ss[3] << ss[4] << ss[5] << "\n";
        cout << "-------" <<  no1.cnt << "\n";
        */

        bool is1=false,is2=false;
        for(int i=0;i<6;i++){
            if(ss[i]=='A' && i==B){
                is1=true;
            }
            if(ss[i]=='B' && i==A){
                is2=true;
            }
        }
        if(is1 && is2){
            cout << no1.cnt;
            return;
        }
        for(int i=0;i<6;i++){
            if(ss[i]==' '){
                continue;
            }
            for(int j=0;j<vt[i].size();j++){
                if(ss[vt[i][j]]==' '){
                    string s1=ss;
                    char ch=s1[i];
                    s1[i]=s1[vt[i][j]];
                    s1[vt[i][j]]=ch;
                    if(st.find(s1)==st.end()){
                        node no2;
                        no2.s=s1;no2.cnt=no1.cnt+1;
                        qu.push(no2);
                        st.insert(s1);
                    }
                }
            }
        }
    }
}

void solve(){
    getline(cin,s1);
    //getchar();
    getline(cin,s2);
    //cout << s1 << " " << s2;
    string s=s1+s2;
    for(int i=0;i<6;i++){
        if(s[i]=='A'){
            A=i;
        }
        else if(s[i]=='B'){
            B=i;
        }
    }
    for(int i=0;i<6;i++){
        vector<int> v;
        vt.push_back(v);
    }
    vt[0].push_back(1);vt[0].push_back(3);
    vt[1].push_back(0);vt[1].push_back(2);vt[1].push_back(4);
    vt[2].push_back(1);vt[2].push_back(5);
    vt[3].push_back(0);vt[3].push_back(4);
    vt[4].push_back(1);vt[4].push_back(3);vt[4].push_back(5);
    vt[5].push_back(2);vt[5].push_back(4);
    bfs(s1,s2);
}

int main(){
    solve();
}