背景

D老师终于在今天（2025/5/24）讲完了DFS和BFS ，借此博客庆祝D老师突破BFS难题。。 。

善良（JiaoHua）的D老师还删掉了20个测试数据（加上了无法到达目标的数据）

（竟是洛谷普及+/提高的题目吗）

---

题目

八数码难题（（1），（2））

题目描述

在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 $0$ 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

输入输出样例 #1

输入 #1

283104765

输出 #1

4

说明/提示

样例解释

图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。

并且可以证明，不存在更优的策略。

---

题解

就是一个$3×3$的数组，从0的地方有四个方向可以移动，求最短几次可以到达：

1 2 3
8 0 4
7 6 5

最短路径，直接BFS起手。既然是$3×3$，那就定义一个$4×4$的数组（🤪）储存棋盘，定义$x$和$y$储存0的坐标，剩下的就和连通块一样了。定义一个结构体包括一个数组、一个0的x、0的y、步数，用来BFS。剩下就是模板了。题解：

题解。

D老师也说过了，其实这道题就难在怎样储存这张棋盘。

---

（洛某的题解都太复杂了，什么A*、双向BFS。。。还是D老师的BFS思路好用）