思路来源：八数码

学习点：

1. 字符矩阵可以压缩为一维，利用坐标变换!!
2. 交换空格
3. 注意点：最终状态，只要A和B在位置上即可，其它位置随意，同八数码不同这一点！
4. cin不能读空格（整行读取getline(cin,s)）

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

string s;
string end;
int a,b; // A,B的位置

int bfs()
{
    queue<string> q;
    q.push(s);
    unordered_map<string,int> dist;
    dist[s] = 0;
    int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};

    int t = b,b = a,a = t; //最终状态，只要A和B在位置上即可，其它位置随意，同八数码不同这一点！

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        int distance = dist[t];
        if(t.find('A') == a && t.find('B') == b) return distance;

        int pos = t.find(' ');
        int x = pos / 3, y = pos % 3;
        //cout << x <<' ' << y << endl;
        for(int i = 0; i < 4;i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if(a >=0 && a < 2 && b >= 0 && b < 3) 
            {
                swap(t[pos],t[a * 3 + b]);
                if(!dist.count(t))
                {
                    q.push(t);
                    dist[t] = distance + 1;
                }
                swap(t[pos],t[a * 3 + b]); // 回溯
            }

        }
    }
}

int main()
{
    for(int i = 0;i < 2;i ++ )
    {
        string a;
        getline(cin,a); // 读取带空格的字符串，整行读取
        s += a;
    }
    //cout << s;
    for(int i = 0;i < 6;i ++ )
        if(s[i] == 'A') a = i;
        else if(s[i] == 'B') b = i;

    cout << bfs();

    return 0;

}