八数码
在一个 3 × 3 的网格中，1 ∼ 8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3 × 3 的网格中
例如：
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列
交换过程如下：
1
2
3
|
1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
|
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换
输入格式
- 输入占一行，将
3 × 3 的初始网格描绘出来
- 例如，如果初始网格如下所示：
则输入为：1 2 3 x 4 6 7 5 8
输出格式
- 输出占一行，包含一个整数，表示最少交换次数
- 如果不存在解决方案，则输出
−1
输入样例
输出样例
分析
抽象为 无权图的最短路径搜索，状态间转换是 交换 x 的位置
- 状态表示
- 使用字符串表示网格状态，目标状态：“12345678x”
- 状态转移
- BFS 求最短步数
- 队列
q 记录待搜索的状态
- 哈希表
d 记录已访问状态，防止重复搜索
- BFS 逐层扩展
- 取出队首状态
tmp
- 遍历
x 的 4 个移动方向：
- 生成新状态
next_state，如果未访问：
- 记录步数
d[next_state] = d[tmp] + 1
- 加入队列
q.push(next_state)
- 若
tmp == end_state，返回步数
- BFS 终止
时间复杂度
时间复杂度 O(9!)
空间复杂度
空间复杂度为 O(9!)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <queue>
#include <unordered_map>
int bfs(std::string& start_state)
{
std::string end_state = "12345678x"; // 目标状态
std::queue<std::string> q; // BFS 队列
std::unordered_map<std::string, int> d; // 记录步数
q.push(start_state);
d[start_state] = 0;
// 方向数组：右、下、左、上
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
while (!q.empty())
{
std::string tmp = q.front();
q.pop();
int distance = d[tmp]; // 取当前状态的步数
if (tmp == end_state)
return distance; // 目标状态，返回最小步数
int k = tmp.find('x'); // 找到 'x' 的索引
int x = k / 3, y = k % 3; // 转换为二维坐标
for (int i = 0; i < 4; ++ i) // 遍历 4 个方向
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) // 确保新位置合法
{
std::swap(tmp[k], tmp[a * 3 + b]); // 交换 'x' 与相邻数字
if (!d.count(tmp)) // 该状态未访问
{
q.push(tmp); // 加入队列
d[tmp] = distance + 1; // 记录步数
}
std::swap(tmp[a * 3 + b], tmp[k]); // 交换回来，恢复原状态
}
}
}
return -1; // 无法到达目标状态
}
int main()
{
std::string start_state;
for (int i = 0; i < 9; ++ i)
{
char c;
std::cin >> c;
start_state += c;
}
std::cout << bfs(start_state) << '\n';
return 0;
}
|
