形式化题目

# 形棋盘固定 24 格，每格写着 $1/2/3$，三种数字各出现 8 次。棋盘由四条笔画构成： 两竖位于第 2、4 列，两横位于第 2、4 行，它们的交叉格只算一次。

输入把 24 个格子按从上到下、同行从左到右的顺序给出，据此给每个格子编号：

1
2
3
4
5
6
7 ·  ·  0  ·  1  ·  ·
 ·  ·  2  ·  3  ·  ·
 4  5  6  7  8  9 10
 ·  · 11  · 12  ·  ·
13 14 15 16 17 18 19
 ·  · 20  · 21  ·  ·
 ·  · 22  · 23  ·  ·

棋盘上可执行 8 种操作 A~H，每种操作沿一条笔画把 7 个格子循环滚动 1 格，首格移到末尾。 8 条笔画（箭头方向就是滚动方向）与它们覆盖的中央格是：

中央 8 格的位置编号是 $6,7,8,11,12,15,16,17$。把棋盘看成 24 元组 $\text{state} \in \{1,2,3\}^{24}$，8 种操作就是 8 个固定的位置置换 $R_A,\dots,R_H$。要求找出 最短的 $k$ 与操作串 $m_1 m_2 \cdots m_k$，使 $R_{m_k}\circ\cdots\circ R_{m_1}(\text{state})$ 的中央 8 个分量全部相等；若有多个长度相同的串，取字典序最小者。

注意读图的两个要点：操作 A~H 的箭头方向对应上表从左到右，而中央格在每条笔画里都处于 下标 2、3、4 的位置——这一点是整道题的突破口。

正解

思路

朴素做法与它的瓶颈

最直接的思路是 BFS：从初始状态逐层扩展，第一次得到“中央同色”的状态就是最短步数。 它逻辑上完全正确，但代价无法接受。状态空间是 $3^{24} \approx 2.8 \times 10^{11}$， 而最短解可以到 11~12 步，BFS 必须在命中目标之前把所有更浅的状态全部展开； 即使每层剪掉逆操作把分支降到 7，第 10 层附近的状态数也已到 $7^{10} \approx 2.8 \times 10^{8}$ 量级。 无论是 128 MB 的内存还是 1000 ms 的时限都撑不住。

瓶颈在于 BFS 按广度展开、必须保存整层状态；而我们真正需要的只是“某一条最短路径”。 既然如此，就把广度优先换成带深度限制的深度优先。

迭代加深：把“最少步数”交给外层

设一个步数上限 bound，只在深度不超过 bound 的范围内做 DFS：

• 若在 bound 内找到了解，那 bound 就是最短步数；
• 若没找到，就把 bound 加 1 重搜。

bound 从某个下界开始逐次 +1，第一次成功的 bound 就是答案。这样内存只剩当前路径 $O(\text{bound})$，和 BFS 的整层状态相比是数量级的改善。

但只有迭代加深还不够：不带任何剪枝时，第 $L$ 层就有 $8 \times 7^{L-1}$ 个节点， 最深一层在 $L=11$ 时约 $2.3 \times 10^9$，$L=12$ 时约 $1.6 \times 10^{10}$，仍然跑不动。 所以必须让“深度限制”真正发挥作用——这就是估价函数。

可采纳估价：$h = 8 - {}$众数个数

中央 8 格中出现次数最多的颜色记作众数，令

现在说明它是可采纳的（即永远不会高估真实剩余步数）。关键在于题目图形的一个结构性质： 每条笔画与中央 8 格的交，恰好是该笔画里下标 2、3、4 的三个连续格。 上表最后一列可以直接验证这一点。滚动一格相当于把整条笔画同时平移一位，于是原来下标 2 的格 移到下标 3、下标 3 的移到下标 4、下标 4 的移出中央，而原先在笔画外的下标 1 的格移进中央 （成为新的下标 2）。也就是说：

一次操作后，中央 8 格只是恰好替换了 1 格（丢掉原下标 4 的格，换成原下标 1 的格）。

既然只换 1 格，那么众数的出现次数每步至多增加 1，h 每步至多减少 1。要把 h 降到 0 至少还需要 h 步，因此 h 是可采纳下界。搜索时：

• g + h > bound 就回退（本分支在现有上限内不可能有解）；
• h == 0 就成功。

这里要抵抗一个诱惑：既然一次操作动 3 个中央格，ceil(h / 3) 看起来是更“聪明”的估价。 它确实也可采纳，但方向反了——它是一个更小（更松）的下界，剪枝更弱。 实测在 30 组数据上，用 h 需要约 2.4 s，而用 ceil(h / 3) 要 69.7 s，差 30 倍。 所以估价就取 h。

字典序最小：靠枚举顺序而不是事后比较

每层都按 A 到 H 的顺序尝试，一旦命中就立刻返回。第 bound 轮首次命中时， 路径长度恰好是 bound（最短），而在所有长度为 bound 的解里，字典序最小的那个一定先被 访问到。所以不需要额外比较，顺序本身就是答案的保证。

剪掉“立刻撤销”

观察操作之间的配对：A↔F、B↔E、C↔H、D↔G 互为逆操作，即 $R_{\overline{m}} \circ R_m = \mathrm{id}$。如果第 $k$ 步走了 $m$、第 $k+1$ 步走了它的逆， 这两步就白走了，删掉它们能得到更短的解。因此任何最短解都不会包含这种相邻对， 搜索时记住上一步是谁、直接跳过它的逆操作即可。

转置剪枝：同一轮内复用已证下界

不同的操作顺序可能把棋盘带到同一个状态（转置）。仅靠估价函数，这些重复状态会被反复展开。 可以在本轮（同一个 bound）内记下已经确证的下界：若某个状态在本轮内被搜完仍未命中， 就说明“从它出发至少还要 bound − g + 1 步”。再次遇到它（可能在不同的深度）时， 取 max(真实估价, 已证下界) 作为 h，剪枝更强。 这个值来自本轮已经穷尽的搜索，不可能高于真实剩余步数，所以仍然可采纳。 实测它把 30 组数据的节点数从约 1585 万降到约 370 万，用时从 7.6 s 降到 2.4 s。

注意缓存的值是相对本轮 bound 推出的下界，所以实现里每轮重新建一张表； 这样既简单，又能保证它不会随着 bound 变大而失真。

用样例验证这条路线

样例第二个用例的初始中央 8 格是 1 1 1 1 2 2 2 2，众数只有 4 个，故 h = 4。 答案 ABHAB 恰好 5 步，逐步推演如下：

可以看到众数的个数从 4 涨到 8，除第 3 步持平（H 顶掉一个 1、又换进一个 3）外每步 +1， 5 步正好走完。2 2 3 2 2 2 2 2 这一步很能说明问题：此时 h = 1 已经很小， 但距离终点还差整整一步，估价没有高估。

代码

LINE 是上表 8 条笔画，CENTER / BACK 分别是中央 8 格与逆操作，ROTATE 把每条笔画 预先编译成一张 24 位取数表，让一次状态转移只花一次函数调用。lower_bound 就是上面的 $h$，solve_case 负责迭代加深与 IDA*，search 是唯一的热点递归。

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103#!/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
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 14:45
# update_at: 2026-10-01 14:57

import sys
from operator import itemgetter

# 棋盘按“从上到下、同行从左到右”编号 0~23；每个操作是一条 7 格首尾相接的环，
# 顺箭头方向滚动一格，即环上每个位置改取它的后继格（末格取首格）。下表就是这 8 条环。
LINE = (
    (0, 2, 6, 11, 15, 20, 22),     # A 最左列自上而下
    (1, 3, 8, 12, 17, 21, 23),     # B 第二列自上而下
    (10, 9, 8, 7, 6, 5, 4),        # C 最下行自右向左
    (19, 18, 17, 16, 15, 14, 13),  # D 最右列自下而上
    (23, 21, 17, 12, 8, 3, 1),     # E 是 B 的反向
    (22, 20, 15, 11, 6, 2, 0),     # F 是 A 的反向
    (13, 14, 15, 16, 17, 18, 19),  # G 是 D 的反向
    (4, 5, 6, 7, 8, 9, 10),        # H 是 C 的反向
)
CENTER = (6, 7, 8, 11, 12, 15, 16, 17)  # 中央 8 格
BACK = (5, 4, 7, 6, 1, 0, 3, 2)         # A↔F、B↔E、C↔H、D↔G，撤销一步就是走它的反向
INF = 10 ** 9

# ROTATE[k][i] = 走完操作 k 之后，格子 i 上的数字来自哪个格子；环外的格子原地不动。
# 把“新状态该取哪些旧格子”压成 8 张 24 位取数表，热循环里一次调用即完成整盘滚动。
ROTATE = []
for line in LINE:
    source = list(range(24))  # 默认每个格子取自己
    for j in range(7):
        source[line[j]] = line[(j + 1) % 7]  # 环上第 j 格改取它的后继，末格取首格
    ROTATE.append(itemgetter(*source))
ROTATE = tuple(ROTATE)
CENTER_OF = itemgetter(*CENTER)


def lower_bound(state: tuple[int, ...]) -> int:
    """中央 8 格最少还要几步才同色。

    每条笔画与中央 8 格的交恰是该笔画里下标 2、3、4 的三个连续格，滚动一格只换掉 1 格，
    所以众数的个数每步至多 +1，即“非众数格数”每步至多 -1，它就是可采纳下界。
    """
    center = CENTER_OF(state)
    return 8 - max(center.count(1), center.count(2), center.count(3))


def solve_case(start: tuple[int, ...]) -> tuple[str, int]:
    """IDA*：先定步数上限，再按 A~H 字典序深搜，首个命中即为最短且字典序最小的解。"""
    bound = lower_bound(start)
    while True:
        path: list[int] = []
        proved: dict[tuple[int, ...], int] = {}  # 本轮已证下界：不同顺序到达同一状态（转置）时复用

        def search(state: tuple[int, ...], g: int, bad: int) -> int:
            """上限 bound 内深搜：找到目标返回 -1，否则返回后继中最小的 f=g+h。"""
            real = lower_bound(state)
            known = proved.get(state, 0)  # 取启发式与已证下界的较大者，剪枝更强但仍可采纳
            h = real if real > known else known
            if g + h > bound:
                return g + h
            if real == 0:
                return -1
            best = INF
            for k in range(8):
                if k == bad:  # 一步一撤销只是原路返回，最短解里不会出现
                    continue
                path.append(k)
                got = search(ROTATE[k](state), g + 1, BACK[k])
                if got == -1:
                    return -1
                path.pop()
                if got < best:
                    best = got
            need = bound - g + 1  # 本状态在上限内走不到目标，说明它还差至少这么多步
            if need > proved.get(state, 0):
                proved[state] = need
            return best

        if search(start, 0, -1) == -1:  # 首个成功的上限就是最短步数
            state = start
            for k in path:
                state = ROTATE[k](state)
            return ''.join(chr(65 + k) for k in path), CENTER_OF(state)[0]
        bound += 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for first in data:
        if first == 0:  # 单独一个 0 表示输入结束
            break
        start = (first, *(next(data) for _ in range(23)))
        moves, color = solve_case(start)
        out.append(moves if moves else 'No moves needed')
        out.append(str(color))
    print('\n'.join(out))


if __name__ == '__main__':
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110/**
 * 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-06 17:42
 * update_at: 2026-10-06 17:42
 */
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll;

// 8 条笔画：首尾相接的 7 个格子编号，按箭头方向滚动一格（末格移到首位）
const int LINE[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},     // A 最左列自上而下
    {1, 3, 8, 12, 17, 21, 23},     // B 第二列自上而下
    {10, 9, 8, 7, 6, 5, 4},        // C 最下行自右向左
    {19, 18, 17, 16, 15, 14, 13},  // D 最右列自下而上
    {23, 21, 17, 12, 8, 3, 1},     // E 是 B 的反向
    {22, 20, 15, 11, 6, 2, 0},     // F 是 A 的反向
    {13, 14, 15, 16, 17, 18, 19},  // G 是 D 的反向
    {4, 5, 6, 7, 8, 9, 10},        // H 是 C 的反向
};
const int CENTER[8] = {6, 7, 8, 11, 12, 15, 16, 17};  // 中央 8 格
const int BACK[8] = {5, 4, 7, 6, 1, 0, 3, 2};         // BACK[k] 是操作 k 的逆操作

int a[24];            // 棋盘 24 个格子的数字（1/2/3），按题面从上到下、同行从左到右编号
int path[32];         // 搜索路径，path[g] = 第 g 步走的操作编号
int bound;            // 当前迭代加深的步数上限
map<ll, int> proved;  // 本轮已证下界缓存：棋盘打包键 -> 从该状态至少还需几步（每轮 bound 重建）

// 把整个棋盘打包成 48 位整数键：每个格子占 2 位，取值只有 1/2/3
ll pack_state() {
    ll key = 0;
    for (int i = 0; i < 24; i++) key |= (ll)a[i] << (2 * i);
    return key;
}

// 可采纳估价 h = 中央 8 格里“非众数格”的个数。
// 每条笔画与中央 8 格的交恰是该笔画里下标 2、3、4 的三格，滚动一格只换掉 1 个中央格，
// 所以众数个数每步至多 +1，h 每步至多 -1，h 就是最少剩余步数的下界。
int h_value() {
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 0; i < 8; i++) {
        if (a[CENTER[i]] == 1) c1++;
        else if (a[CENTER[i]] == 2) c2++;
        else c3++;
    }
    return 8 - max(c1, max(c2, c3));
}

// 沿笔画 k 顺箭头滚动一格：环上第 j 格改取第 j+1 格的数字，末格改取原首格
void do_op(int k) {
    int first = a[LINE[k][0]];
    for (int j = 0; j < 6; j++) a[LINE[k][j]] = a[LINE[k][j + 1]];
    a[LINE[k][6]] = first;
}

// 撤销操作 k：逆着滚动方向把数字移回去
void undo_op(int k) {
    int last = a[LINE[k][6]];
    for (int j = 6; j > 0; j--) a[LINE[k][j]] = a[LINE[k][j - 1]];
    a[LINE[k][0]] = last;
}

// 在步数上限 bound 内深搜：找到解返回 true（路径存在 path[0..bound-1]），否则返回 false
bool dfs(int g, int bad) {
    int real = h_value();
    ll key = pack_state();
    int known = 0;
    map<ll, int>::iterator it = proved.find(key);
    if (it != proved.end()) known = it->second;
    // 取真实估价与已证下界的较大者：剪枝更强，但都来自本轮已穷尽的搜索，仍可采纳
    int h = real > known ? real : known;
    if (g + h > bound) return false;  // 本分支在上限内不可能有解
    if (real == 0) return true;       // 中央 8 格已同色
    for (int k = 0; k < 8; k++) {     // 按 A~H 字典序尝试，命中即得最短且字典序最小的解
        if (k == bad) continue;       // 走上一步的逆操作等于原路返回，最短解里不会出现
        path[g] = k;
        do_op(k);
        if (dfs(g + 1, BACK[k])) return true;
        undo_op(k);
    }
    // 本状态在剩余步数内走不到目标：它至少还差 bound - g + 1 步，记下来供同轮其它分支复用
    int need = bound - g + 1;
    if (need > known) proved[key] = need;
    return false;
}

int main() {
    int first;
    while (scanf("%d", &first) == 1 && first != 0) {
        a[0] = first;
        for (int i = 1; i < 24; i++) scanf("%d", &a[i]);
        bound = h_value();  // 步数上限从估价下界开始逐次 +1
        while (!dfs(0, -1)) {
            bound++;
            proved.clear();  // 已证下界相对当前 bound 才有效，每轮重建
        }
        if (bound == 0) printf("No moves needed\n");
        else {
            for (int i = 0; i < bound; i++) putchar('A' + path[i]);
            putchar('\n');
        }
        printf("%d\n", a[CENTER[0]]);  // dfs 命中时棋盘已是解状态，中央同色
    }
    return 0;
}

复杂度

• 时间复杂度：$O(T \cdot 7^{L})$，其中 $T \leqslant 30$ 是用例数、$L$ 是最短步数（实测最大 11）。 根节点有 8 个分支，之后每层都剪掉了上一步的逆操作，分支因子降到 7；迭代加深重复搜索 更浅的层只带来约 $7/6$ 的常数因子，不改变量级。实际展开节点数约 400 万（30 组）， 远低于这个上界。
• 空间复杂度：递归深度与路径长度都是 $O(L)$；主要占用是轮内下界缓存 proved （每轮 bound 递增时重建），实测峰值约 65 MB，在 128 MB 之内。
• 作为对比，朴素 BFS 的时间和空间都是整层状态规模（$10^8$ 量级），完全不可行。

总结

这道题的核心不是“怎么枚举 8 种操作”，而是怎么把搜索深度受限、又不漏掉最优解。

推导链条是：BFS 会因为必须保存整层状态而爆炸 → 改成带深度上限 bound 的迭代加深 DFS， 内存降到 $O(L)$ → 但裸 DFS 的节点数仍随层数指数增长（第 $L$ 层 $8 \times 7^{L-1}$）， 所以需要可采纳估价来剪枝 → 利用“每条笔画与中央 8 格的交恰好是下标 2、3、4”这一图形性质，得出一次操作只替换 1 个 中央格，于是 $h = 8 - {}$众数个数 是可采纳下界 → 再补两个细节：按 A~H 顺序枚举并 命中即返回，天然得到字典序最小；剪掉上一步的逆操作，砍掉 $1/8$ 的无效分支。

容易踩的坑有三个：一是把估价取成 ceil(h/3)，方向搞反导致剪枝变弱（实测慢 30 倍）； 二是剪枝时误写成“跳过和上一步相同的操作”（应该是跳过它的逆操作），会剪掉大量最优解； 三是输出格式，零步时要输出 No moves needed 而不是空行。

图示解析

整条控制流如下：外层不断抬高 bound，内层做带剪枝的深度优先搜索，命中即一路返回。

flowchart TD
    A["读入 state"] --> B["bound = h(state)"]
    B --> C["清空 path 与下界缓存 proved"]
    C --> D{"search(state, g=0, bad=无)"}
    D -->|"h == 0"| E["命中：返回 path 的操作串"]
    D -->|"g + h > bound"| F["本分支剪掉"]
    D -->|"还有分支"| G["按 A~H 顺序试 k"]
    G -->|"k 是上一步的逆"| G
    G -->|"否则递归 search"| D
    F --> H{"本轮所有分支都剪掉/失败？"}
    G --> H
    H -->|"是"| I["bound = bound + 1，重搜"]
    I --> C
    H -->|"否"| E
    E --> J["输出操作串（空串则为 No moves needed）与中央数字"]

读者应重点看两处：一是 h == 0 的判定与 g + h > bound 的剪枝共用同一个 h， 前者是终止条件、后者是剪枝条件；二是只有外层在动 bound，内层搜索从不放宽深度， 所以第一次命中的路径长度就是最短步数。图中“k 是上一步的逆”这条自环对应代码里的 if k == bad: continue，它把分支因子从 8 降到 7。