题目描述

还记得小时候在生日派对上玩过的那些数字拼图游戏吗？现在它们以数字化的形式回归了！如今的孩子们享受着科技带来的便利，游戏自然也不例外。

为此，Wiltin' Badley公司决定发布这款经典拼图游戏的21世纪版本，命名为"缺失的拼图2001"。作为现代化版本，游戏将配备一个软件辅助工具，用于评估玩家解决拼图所需的技巧水平。该软件允许玩家输入初始棋盘配置和期望的最终配置，然后判断是否能在指定步数内完成拼图。若可解，软件还将给出最优解所需的步数。你被聘为软件工程师来开发这个工具。

输入格式

输入包含最多10组数据，每组格式如下（数据组间无空行）：

1. 起始行 - "START D N"，其中$3 \leq D \leq 10$表示棋盘维度，$0 \leq N \leq 15$表示期望的最大步数
2. 初始棋盘 - $D \times D$矩阵，包含$1$到$(D^2-1)$的整数和1个'X'（空缺位）
3. 目标棋盘 - 同规格的$D \times D$矩阵，表示完成状态
4. 结束行 - "END"

注意：

• 两个棋盘都包含$1$到$(D^2-1)$的所有整数（无重复）和1个'X'
• 'X'只能与相邻数字（上、下、左、右）交换位置

输出格式

每组数据输出一行，格式为：

• 若可解：SOLVABLE WITHIN [最优步数] MOVES
• 若不可解：NOT SOLVABLE WITHIN [指定步数] MOVES

输入样例1

START 3 4
1 5 2
4 X 3
7 8 6
1 2 3
4 5 6
7 8 X
END
START 3 3
1 2 3 
7 X 8
6 5 4
1 2 3 
8 X 4
7 6 5
END
START 4 10
1 X 2 4
5 6 3 7
9 10 11 8
12 13 14 15
1 2 3 4
5 6 7 8
9 10 X 11
12 13 14 15
END

输出样例1

SOLVABLE WITHIN 4 MOVES

NOT SOLVABLE WITHIN 3 MOVES

SOLVABLE WITHIN 5 MOVES

来源

South Central USA 2001