AcWing 845. 八数码
原题链接
中等
作者:
梦都会空
,
2021-12-06 18:05:18
,
所有人可见
,
阅读 149
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
queue<string> q;
unordered_map<string, int> d;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
const string ed = "12345678x";
int bfs(string state) {
q.push(state);
d[state] = 0;
while (q.size() > 0) {
auto t = q.front();
q.pop();
int idx = t.find('x');
int a = idx / 3, b = idx % 3;
int distance = d[t];
if (t == ed)
return d[t];
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];//进行移动时需要二维化
swap(t[x * 3 + y], t[idx]);
if (x >= 0 && x < 3 && y >= 0 && y < 3 && !d[t]) {
d[t] = distance + 1;
q.push(t);
}
swap(t[x * 3 + y], t[idx]);
}
}
return -1;
}
int main() {
string state;
char c;
for (int i = 0; i < 9; i++) {//二维->一维
cin >> c;
state += c;
}
cout << bfs(state)<<endl;
}