You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

95 lines
2.8 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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;
}