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