【题目来源】
洛谷：P1379 八数码难题 - 洛谷
【题目描述】
在 \(3\times 3\) 的棋盘上，摆有八个棋子，每个棋子上标有 \(1\) 至 \(8\) 的某一数字。棋盘中留有一个空格，空格用 \(0\) 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 \(123804765\)），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
【输入】
输入初始状态，一行九个数字，空格用 \(0\) 表示。
【输出】
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。
【输入样例】
283104765
【输出样例】
4
【算法标签】
《洛谷 P1379 八数码难题》 #搜索# #枚举# #哈希,hash# #A*算法# #福建省历届夏令营#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 使用unordered_map来存储状态到步数的映射
unordered_map<string, int> d; // 存储每个状态对应的步数
queue<string> q; // BFS队列
string s; // 初始状态字符串
int ans; // 结果（最少步数）// 方向数组：上、右、下、左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};// 广度优先搜索函数
int bfs(string str)
{// 初始状态入队q.push(str);// 目标状态string end = "123804765"; // 目标状态：1 2 3// 8 0 4// 7 6 5// BFS主循环while (q.size()) {auto s = q.front(); // 获取队首状态q.pop();// 如果到达目标状态，返回步数if (s == end) return d[s]; // 到达目标// 找到'0'（空格）的位置int k = s.find('0');// 将一维索引转换为二维坐标int x = k / 3, y = k % 3;// 尝试四个方向的移动for (int i = 0; i < 4; i++) {int xx = x + dx[i]; // 新位置的x坐标int yy = y + dy[i]; // 新位置的y坐标// 检查新位置是否在3x3网格内if (xx < 0 || xx >= 3 || yy < 0 || yy >= 3) continue;int dis = d[s]; // 记录当前状态的步数// 交换'0'和相邻位置的数字swap(s[k], s[xx * 3 + yy]); // 生成新状态// 如果新状态未被访问过if (!d.count(s)) {d[s] = dis + 1; // 记录步数q.push(s); // 新状态入队}// 还原状态，以便尝试下一个方向swap(s[xx * 3 + yy], s[k]); // 还原}}return -1; // 如果无法到达目标，返回-1
}int main()
{// 输入初始状态cin >> s;// 初始状态步数为0d[s] = 0;// 执行BFS搜索ans = bfs(s);// 输出结果cout << ans;return 0;
}
【运行结果】
283104765
4