状态只有 8! 个，把每个排列看作节点、A/B/C 三种操作看作边，从基本状态 12345678 BFS，邻居按 A→B→C 顺序扩展且只在首达时记前驱，回溯即得字典序最小的最短操作序列。
OJ: roj
题目 ID: 1449
难度:普及-
标签:BFS状态压缩置换
创建: 2026-09-30 11:11
更新: 2026-10-05 23:47
题目描述
给定
输入一行 8 个整数表示目标状态；输出最短操作序列的长度，以及字典序最小的最短操作串（除最后一行外每行 60 个字符）。样例：输入 2 6 8 4 5 7 3 1，输出 7 / BCABCCB。
思路
状态总数只有 12345678 做 BFS；邻居固定按 A、B、C 顺序扩展且只在首次入队时记前驱，首次到达目标的路径就是字典序最小的最短操作序列，回溯前驱输出即可。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# 魔板 Magic Squares 题解
# create_at: 2026-07-05 22:00
# update_at: 2026-07-05 22:00
import sys
from collections import deque
# 三种操作在顺时针序列上的下标重排：s' = tuple(s[i] for i in perm)
PERMS = [
(7, 6, 5, 4, 3, 2, 1, 0), # A：交换上下两行，序列整体翻转
(3, 0, 1, 2, 5, 6, 7, 4), # B：最右列插入最左列
(0, 6, 1, 3, 4, 2, 5, 7), # C：中央 2x2 顺时针旋转
]
START = tuple(range(1, 9)) # 基本状态 1..8
def solve() -> None:
target = tuple(map(int, sys.stdin.read().split())) # 目标状态，顺时针序列
# BFS：按 A、B、C 顺序扩展，首次到达即为字典序最小的最短操作序列
prev: dict[tuple[int, ...], tuple[tuple[int, ...], str]] = {}
queue = deque([START])
while queue:
state = queue.popleft()
if state == target:
break
for letter, perm in zip("ABC", PERMS):
nxt = tuple(state[i] for i in perm)
if nxt not in prev:
prev[nxt] = (state, letter)
queue.append(nxt)
# 回溯还原路径
path: list[str] = []
state = target
while state != START:
state, letter = prev[state]
path.append(letter)
answer = ''.join(reversed(path))
print(len(answer))
# 除最后一行外每行 60 个字符
print('\n'.join(answer[i:i + 60] for i in range(0, len(answer), 60)))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 23:47
* update_at: 2026-10-05 23:47
*/
// main.cpp：BFS 求魔板从基本状态到目标状态的最短字典序操作序列。
#include <iostream>
#include <map>
#include <queue>
#include <string>
typedef long long ll;
// 三种操作在顺时针序列上的下标重排：新序列第 i 位来自旧序列 OPS[op][i] 位
const int OPS[3][8] = {
{7, 6, 5, 4, 3, 2, 1, 0}, // A：交换上下两行，序列整体翻转
{3, 0, 1, 2, 5, 6, 7, 4}, // B：最右列插入最左列
{0, 6, 1, 3, 4, 2, 5, 7} // C：中央 2x2 顺时针旋转
};
const int POW9[8] = {1, 9, 81, 729, 6561, 59049, 531441, 4782969}; // 9 进制各位权值
std::map<int, int> prev_state; // prev_state[状态] = 前驱状态
std::map<int, char> prev_op; // prev_op[状态] = 到达该状态所用的操作字母
std::queue<int> bfs_queue; // BFS 队列，存编码后的状态
// 把 8 位排列编码成 9 进制整数；每位是 1~8，不含 0，故编码唯一
int encode(int s[8]) {
int code = 0;
for (int i = 0; i < 8; i++) {
code += s[i] * POW9[i];
}
return code;
}
// 把 9 进制编码还原成 8 位排列
void decode(int code, int s[8]) {
for (int i = 0; i < 8; i++) {
s[i] = code % 9;
code /= 9;
}
}
int main() {
int target[8];
for (int i = 0; i < 8; i++) {
std::cin >> target[i];
}
int start[8] = {1, 2, 3, 4, 5, 6, 7, 8}; // 基本状态
int start_code = encode(start);
int target_code = encode(target);
// BFS：邻居固定按 A、B、C 顺序扩展，且只在首次入队时记前驱，
// 因此首次到达目标时的路径就是字典序最小的最短操作序列
prev_state[start_code] = -1;
bfs_queue.push(start_code);
while (!bfs_queue.empty()) {
int cur = bfs_queue.front();
bfs_queue.pop();
if (cur == target_code) {
break;
}
int s[8];
decode(cur, s);
for (int op = 0; op < 3; op++) {
int nxt[8];
for (int i = 0; i < 8; i++) {
nxt[i] = s[OPS[op][i]];
}
int nxt_code = encode(nxt);
if (prev_state.find(nxt_code) == prev_state.end()) {
prev_state[nxt_code] = cur;
prev_op[nxt_code] = 'A' + op;
bfs_queue.push(nxt_code);
}
}
}
// 从目标沿前驱回溯到基本状态，得到的是逆序序列
std::string answer;
int cur = target_code;
while (cur != start_code) {
answer += prev_op[cur];
cur = prev_state[cur];
}
ll len = answer.size();
for (ll i = 0; i < len / 2; i++) {
char tmp = answer[i];
answer[i] = answer[len - 1 - i];
answer[len - 1 - i] = tmp;
}
std::cout << len << "\n";
// 除最后一行外每行输出 60 个字符
for (ll i = 0; i < len; i += 60) {
std::cout << answer.substr(i, 60) << "\n";
}
return 0;
}