|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
|
|
|
typedef unordered_map<string, int> MSI;
|
|
|
typedef unordered_map<string, pair<char, string>> MSP;
|
|
|
|
|
|
string st, ed = "12345678x";
|
|
|
|
|
|
// 上下左右
|
|
|
char op[] = {'u', 'd', 'l', 'r'};
|
|
|
int dx[] = {-1, 1, 0, 0};
|
|
|
int dy[] = {0, 0, -1, 1};
|
|
|
struct Node {
|
|
|
int dist;
|
|
|
string str;
|
|
|
const bool operator<(const Node &b) const {
|
|
|
return b.dist < dist;
|
|
|
}
|
|
|
};
|
|
|
// 前驱
|
|
|
MSP pre;
|
|
|
MSI dist;
|
|
|
priority_queue<Node> q;
|
|
|
|
|
|
// 估值函数【每个位置的现实值与理想值的曼哈顿距离差值和】
|
|
|
int f(string str) {
|
|
|
int res = 0;
|
|
|
for (int i = 0; i < str.size(); i++)
|
|
|
if (str[i] != 'x') {
|
|
|
int t = str[i] - '1'; // str[i]对应的数字，应该在下标从0开始的字符串哪个位置
|
|
|
// ① 利用除3模3大法，将下标从0开始的坐标转换为二维坐标,并计算理想值与目标值的曼哈顿距离
|
|
|
// ② 曼哈顿距离的累加值才是当前状态与理想状态的整体差距
|
|
|
res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
|
|
|
}
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
string astar() {
|
|
|
// 将估价函数与字符串形成数对，放入到优先队列中
|
|
|
q.push({f(st), st});
|
|
|
dist[st] = 0; // 记录距离为0
|
|
|
|
|
|
while (q.size()) {
|
|
|
string t = q.top().str;
|
|
|
q.pop();
|
|
|
|
|
|
if (t == ed) break;
|
|
|
|
|
|
int k = t.find('x');
|
|
|
int tx = k / 3, ty = k % 3;
|
|
|
for (int i = 0; i < 4; i++) { // 枚举udlr
|
|
|
int x = tx + dx[i], y = ty + dy[i];
|
|
|
if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
|
|
|
string v = t; // 将t字符串复制出来一个，生成 v字符串
|
|
|
swap(v[k], v[x * 3 + y]); // 将原字符串中x与目标位置进行交换，生成新的目标状态字符串v
|
|
|
|
|
|
if (dist[v]) continue;
|
|
|
dist[v] = dist[t] + 1; // 更新最小值
|
|
|
q.push({dist[v] + f(v), v}); // 将新的估价函数计算更新，重新入队列
|
|
|
pre[v] = {op[i], t};
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 将路径倒转过来
|
|
|
string res;
|
|
|
while (ed != st) {
|
|
|
res += pre[ed].first;
|
|
|
ed = pre[ed].second;
|
|
|
}
|
|
|
reverse(res.begin(), res.end());
|
|
|
return res;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
char c;
|
|
|
for (int i = 0; i < 9; i++) cin >> c, st += c;
|
|
|
|
|
|
// 八数码定理
|
|
|
int nums = 0;
|
|
|
for (int i = 0; i < 9; i++) {
|
|
|
if (st[i] == 'x') continue;
|
|
|
for (int j = i + 1; j < 9; j++) {
|
|
|
if (st[j] == 'x') continue;
|
|
|
if (st[j] < st[i]) nums++; // 逆序数
|
|
|
}
|
|
|
}
|
|
|
// 奇数个逆序对，无解
|
|
|
if (nums & 1)
|
|
|
puts("unsolvable");
|
|
|
else
|
|
|
cout << astar() << endl; // 运行astar算法，返回最短距离
|
|
|
|
|
|
return 0;
|
|
|
}
|
