|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 5;
|
|
|
|
|
|
// 当前串，哪个操作，前序串
|
|
|
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, MSP &bPre) { // bPre在下面代码中未用到，但为了保持对称性，保留了这个参数
|
|
|
string t = q.front();
|
|
|
q.pop();
|
|
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
int k = t.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 u = t;
|
|
|
swap(u[x * 3 + y], u[k]); // x与目标位置交换一下
|
|
|
|
|
|
if (da[u]) continue; //如果搜索过
|
|
|
aPre[u] = {op[i], t}; //没有搜索过时，一定要马上记录它的前驱！！！不能因为它还没有进入队列就不先记录！！！
|
|
|
// 原因：因为两段式搜索，最终要输出完整的路径，否则就会出现中间缺一条线的情况，比如 ○→○→○ ←(这是这个箭头) ○←○←○，
|
|
|
|
|
|
if (db[u]) { //如果对方已经搜到了
|
|
|
mid = u; //将中间态保存到全局变量中，方便以后的操作
|
|
|
return da[u] + db[u] - 1; //返回中间点距离起点、终点距离和-1
|
|
|
}
|
|
|
|
|
|
da[u] = da[t] + 1; //距离增加1
|
|
|
q.push(u);
|
|
|
}
|
|
|
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, bPre); //从a中取状态进行扩展
|
|
|
else
|
|
|
t = extend(qb, db, da, bPre, aPre);
|
|
|
if (t > 0) break;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
cin.tie(0), ios::sync_with_stdio(false);
|
|
|
|
|
|
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();
|
|
|
|
|
|
//输出路径
|
|
|
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;
|
|
|
} |
