AcWing 845. 八数码
原题链接
中等
作者:
我是java同学
,
2023-02-06 22:46:37
,
所有人可见
,
阅读 170
bfs
- 问题转化:把所有状态看成
图
的节点,如果一个点能到另一个点,就可以在这两个点之间连接一条边,权重就是1。而从起点到中点就可以连成一个图,权重就是最终的步数。
- 难点:
- 状态表示(
3 * 3
矩阵)复杂,如何把状态存到队列
- 如何记录每个状态的距离——
哈希表
- 如何状态转移
- 字符串恢复成矩阵
- 移动(转移状态)
- 将矩阵恢复成字符串
- 细节
- 最先被搜到的一定是步数最少的
- 一维数组的下标转化为二维数组的下标,以及二维转一维
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int bfs(string start)
{
string end = "12345678x";
queue<string> q;
unordered_map<string, int> d;
q.push(start);
d[start] = 0;
while (q.size())
{
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end) return distance;
int k = t.find('x');
int x = k / 3, y = k % 3;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3)
{
swap(t[k], t[a * 3 + b]);
if (!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main()
{
string start;
for (int i = 0; i < 9; i ++ )
{
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
}