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.

114 lines
3.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, pair<char, string>> MSP;
// 字符串,步数
typedef unordered_map<string, int> MSI;
// 操作符,上下左右
char op[] = {'u', 'd', 'l', 'r'};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 记录前驱路径
MSP aPre, bPre;
// 记录距离
MSI da, db;
string mid; // 两个队列互相查看着搜索当在对方HASH表中命中时最终的那个两边都有的中间状态是什么样的字符串
queue<string> qa, qb; // 两个队列,分别用于存放从起点走出来的字符串和从终点走出来的字符串
int extend(queue<string> &q, MSI &da, MSI &db, MSP &aPre) {
string u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int k = u.find('x'); // 在字符串t中查找x的索引位置
int tx = k / 3, ty = k % 3; // 映射的二维数组中的行与列
int x = tx + dx[i], y = ty + dy[i]; // 目标位置
if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
string v = u;
swap(v[x * 3 + y], v[k]); // x与目标位置交换一下
if (da[v]) continue; // 如果搜索过
aPre[v] = {op[i], u}; // 没有搜索过时,一定要马上记录它的前驱!!!不能因为它还没有进入队列就不先记录!!!
// 原因:因为两段式搜索,最终要输出完整的路径,否则就会出现中间缺一条线的情况,比如 ○→○→○ ←(这是这个箭头) ○←○←○,
if (db[v]) { // 如果对方已经搜到了
mid = v; // 将中间态保存到全局变量中,方便以后的操作
return da[v] + db[v] - 1; // 返回中间点距离起点、终点距离和-1
}
da[v] = da[u] + 1; // 距离增加1
q.push(v);
}
return -1; // 如果本次扩展没有找到连接前后的字符串,那就返回-1表示还需要继续找
}
// 出发状态,目标状态
string st, ed = "12345678x";
void bfs() {
qa.push(st);
da[st] = 0;
qb.push(ed);
db[ed] = 0;
while (qa.size() && qb.size()) { // 双端宽搜套路
int t;
if (qa.size() <= qb.size()) // 这里面是一个双向bfs的优化策略两个队列谁小就谁使劲跑
t = extend(qa, da, db, aPre); // 从a中取状态进行扩展
else
t = extend(qb, db, da, bPre);
if (t > 0) break;
}
}
int main() {
char c;
for (int i = 1; i <= 9; i++) cin >> c, st += c;
// 八数码定理:检查逆序对数量
int nums = 0;
for (int i = 0; i < 9; i++) {
if (st[i] == 'x') continue; // 保证不是x
for (int j = i + 1; j < 9; j++) {
if (st[j] == 'x') continue; // 保证不是x
if (st[j] < st[i]) nums++; // 逆序数
}
}
// 如果逆序对数量是奇数个,则输出-1
if (nums & 1)
puts("unsolvable");
else {
// 双向宽搜
bfs();
// 两段式输出
// ① 输出前半段与传统BFS输出路径无异
string res;
string t = mid;
while (t != st) {
res += aPre[t].first;
t = aPre[t].second;
}
reverse(res.begin(), res.end());
// ② 输出后半段,因宽搜的方向问题,需要逆着来
t = mid;
while (t != ed) {
char cmd = bPre[t].first;
if (cmd == 'u' || cmd == 'd') cmd = 'u' + 'd' - cmd;
if (cmd == 'l' || cmd == 'r') cmd = 'l' + 'r' - cmd;
res += cmd;
t = bPre[t].second;
}
// 输出
cout << res << endl;
}
return 0;
}