思路与算法

以顺时针的8字符串表示棋盘。从12345678开始BFS，按A、B、C顺序生成邻居，首次访问时记录完整操作串。目标首次出队时输出长度与操作串。A是整个串逆序；B和C按题目示意图的位置置换。

正确性说明

每个合法操作都是状态图的一条单位边，BFS首次发现目标得到最少步数。同层按ABC扩展，且仅保留每状态首次路径，使相同步数的路径按字典序被发现，所以目标路径也为字典序最小。置换保留所有8个数字，状态空间恰为8!种排列。

复杂度

最多V=40320状态，每个3条边。设最长记录操作串长度D，保存和复制路径的上界O(VD)，BFS时间O(VD)，空间O(VD)；本题有限状态图D很小。哈希表与队列动态初始化O(1)，所有状态创建计入总界。

易错点

输入按顺时针编号，底行与字符串后4位方向相反。公开样例把长度和操作串排在同一行，但输出定义明确Line1/Line2，题面已附排版说明。目标为初始状态时长度0，第二行为空。独立答案使用物理2×4矩阵、反向BFS距离和正向字典序恢复。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
string moveState(string s, int op) {
    int p[3][8] = {{7, 6, 5, 4, 3, 2, 1, 0}, {3, 0, 1, 2, 5, 6, 7, 4}, {0, 6, 1, 3, 4, 2, 5, 7}};
    string t = s;
    for (int i = 0; i < 8; ++i)
        t[i] = s[p[op][i]];
    return t;
}
int main() {
    string goal;
    for (int i = 0, x; i < 8; ++i) {
        cin >> x;
        goal += char('0' + x);
    }
    queue<string> q;
    unordered_map<string, string> path;
    string start = "12345678";
    q.push(start);
    path[start] = "";
    while (!q.empty()) {
        string u = q.front();
        q.pop();
        if (u == goal) {
            string answer = path[u];
            cout << answer.size() << '\n';
            for (size_t i = 0; i < answer.size(); i += 60)
                cout << answer.substr(i, 60) << '\n';
            if (answer.empty())
                cout << '\n';
            return 0;
        }
        for (int op = 0; op < 3; ++op) {
            string v = moveState(u, op);
            if (!path.count(v)) {
                path[v] = path[u] + char('A' + op);
                q.push(v);
            }
        }
    }
}