题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 x 来表示。空格周围的棋子可以移到空格中。移动方法有四种：

• r：使空格右移，也就是将空格右边的棋子移动到空格处；
• d：使空格下移，也就是将空格上边的棋子移动到空格处；
• l：使空格左移，也就是将空格左边的棋子移动到空格处；
• u：使空格上移，也就是将空格上边的棋子移动到空格处。

要求解的问题是：给出一种初始布局，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

对于八数码问题，目标布局如下：

输入格式

输入初始状态，一行九个数字，空格用 x 表示，依次表示每行从左向右的数字。

输出格式

输出一种移动次数最少的、可行的移动方案。保证测试数据中无特殊无法到达目标状态数据。

6 4 7 8 5 x 3 2 1

uldldrurdluulddrurulldrrulldrdr