学习目标与前置知识

• 明确搜索状态、合法选择与终止条件，完成能通过本地判题的 C++17 解答。
• 用边界输入解释本题的常见错误，说明剪枝或最短距离为何正确。
• 前置：本章相关知识，C++ 函数、容器、递归，以及题目所用的队列或位运算。

题目描述

在5×5棋盘上有12个黑色棋子、12个白色棋子和一个空位。每步将一个棋子按照马的走法跳到空位，相当于空位与相距一横两竖或两横一竖的棋子交换。黑色用1表示，白色用0表示，空位用*表示。求到目标棋盘的最少步数，最多允许15步。

本 Lab 保留原题的标准输入/输出合同。

目标棋盘

11111
01111
00*11
00001
00000

输入格式

第一行测试组数T；每组5行，每行5个连续字符0、1或*。

输出格式

每组输出一行最少步数；如果15步内无法到达目标，输出 -1。目标棋盘为 11111 / 01111 / 00*11 / 00001 / 00000（斜线只是行分隔说明）。

数据范围

1 <= T <= 10，每组恰有12个0、12个1和一个*。上限15步包含恰好15步。

样例输入

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

样例输出

7
-1

状态与边界

IDA*逐渐增大深度上限，非空棋子的错位数给出至少还需多少步；记录本轮到同一棋盘的最小深度。

把空位也计入错位数后直接当步数下界可能高估；要避免立即撤销上一步，且不同测试组与深度轮次不能沿用错误的访问标记。

复杂度目标

深度上限D=15，保守时间 O(25 * 8^D)，剪枝后依赖实际状态；递归空间 O(D)，本轮去重表最坏 O(25 * 8^D)。

编写与测试

修改 student/main.cpp 中的 solve，保留读写框架。标准输出只保留答案，调试信息写入标准错误。测试清单和分值以 tests/cases.json 为准，总分 100 分，输入均符合本页约定。

在仓库根目录执行：

pnpm lab:run -- labs/chapter-15/exercise/E-15-21-knight-spirit
pnpm lab:score -- labs/chapter-15/exercise/E-15-21-knight-spirit

进入本 Lab 目录后也可以运行 make run。作者与 CI 严格核验：

pnpm lab:verify -- labs/chapter-15/exercise/E-15-21-knight-spirit

完成清单

• 学生程序编译成功，严格评分为 100/100。
• 能解释搜索状态、终止、撤销或剪枝，以及复杂度。
• 构造一个能击穿常见错误的最小输入。
• 答案的数量、顺序和空结果处理符合本页约定。

思考与复盘

1. 哪些信息必须随当前路径恢复，哪些信息可以保留？
2. 去掉本题的一条约束或剪枝，会影响正确性还是只影响效率？请用具体输入说明。
3. 输入达到上限时，时间、递归深度和输出大小分别如何增长？

题目来源与课程化说明

来源：洛谷 P2324 骑士精神。题面按课程环境重新表述，参考实现和测试独立编写，不复制第三方题解或隐藏测试。完整参考代码位于 solution/main.cpp。