分析

• 思路：首先将”12345678”放到队列的队头，然后用宽搜搜索可以到达的状态，直到搜到终点为止。

• 每一次扩展的时候分别做一下A、B、C三种操作，做完之后得到一个字符串，然后判断这个字符串是否被搜到过，如果没有搜到过的话，把它的距离更新一下，然后存到队列中。

• 因为要输出方案，我们记录一下每个状态是从哪个状态更新过来的即可。

• 如何保证存在多个方案时，输出字典序最小的方案呢？我们在扩展的时候按照A、B、C三种方案进行扩展即可。可以使用数学归纳法证明：任意时刻按照A、B、C三种方案进行扩展得到的序列字典序是最小的。

（1）刚开始序列为空，归纳假设显然成立。

（2）假设某一时刻上述归纳假设成立，那么考虑下一时刻：

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

using namespace std;

char g[2][4];  // 盘面
// pre[s2] = {'A', s1}  表示：s1变到s2是通过A方案实现的
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;

// 将string转化为盘面
void set(string state) {
    for (int i = 0; i < 4; i++) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i--, j++) g[1][j] = state[i];
}

// 将盘面转化为string
string get() {
    string res;
    for (int i = 0; i < 4; i++) res += g[0][i];
    for (int i = 3; i >= 0; i--) res += g[1][i];
    return res;
}

string move0(string state) {
    set(state);
    for (int i = 0; i < 4; i++) swap(g[0][i], g[1][i]);
    return get();
}

string move1(string state) {
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for (int i = 3; i > 0; i--) {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state) {
    set(state);
    int v = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
}

int bfs(string start, string end) {

    if (start == end) return 0;

    queue<string> q;
    q.push(start);
    dist[start] = 0;

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

        string m[3];
        m[0] = move0(t);  // 'A'
        m[1] = move1(t);  // 'B'
        m[2] = move2(t);  // 'C'

        for (int i = 0; i < 3; i++) 
            if (!dist.count(m[i])) {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {i + 'A', t};
                q.push(m[i]);
                if (m[i] == end) return dist[end];
            }
    }
    return -1;
}


int main() {

    int x;
    string start, end;
    for (int i = 0; i < 8; i++) {
        cin >> x;
        end += char(x + '0');
    }
    for (int i = 1; i <= 8; i++) start += char('0' + i);

    int step = bfs(start, end);

    cout << step << endl;

    string res;
    while (end != start) {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if (step > 0) cout << res << endl;

    return 0;
}