|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef unordered_map<string, int> MSI;
|
|
|
typedef unordered_map<string, pair<char, string>> MSP;
|
|
|
// 无脑BFS解法
|
|
|
// 2997 ms 可以AC掉本题
|
|
|
string st, ed = "12345678x";
|
|
|
// 上右下左 四个方向
|
|
|
int dx[] = {-1, 0, 1, 0};
|
|
|
int dy[] = {0, 1, 0, -1};
|
|
|
char op[] = {'u', 'r', 'd', 'l'};
|
|
|
MSP pre; // 字符串，前驱操作符，前驱字符串
|
|
|
|
|
|
void bfs() {
|
|
|
queue<string> q;
|
|
|
MSI dist; // 标识某个状态是否用过，如果用过，那么记录的最短距离是多少
|
|
|
|
|
|
// 入队列
|
|
|
q.push(st);
|
|
|
dist[st] = 0; // 记录出发点最短距离
|
|
|
|
|
|
// 开始bfs
|
|
|
while (q.size()) {
|
|
|
// 取出队头字符串
|
|
|
string t = q.front();
|
|
|
q.pop();
|
|
|
|
|
|
// 如果到达最终状态，结束
|
|
|
if (t == ed) {
|
|
|
string res;
|
|
|
while (ed != st) {
|
|
|
res += pre[ed].first;
|
|
|
ed = pre[ed].second;
|
|
|
}
|
|
|
for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
|
|
|
break;
|
|
|
}
|
|
|
int d = dist[t]; // 现在记录的最短路径长度
|
|
|
|
|
|
int k = t.find('x'); // 在字符串t中查找x的索引位置
|
|
|
int tx = k / 3, ty = k % 3; // 映射的二维数组中的行与列
|
|
|
for (int i = 0; i < 4; i++) { // 枚举四个方向
|
|
|
int x = tx + dx[i], y = ty + dy[i]; // 目标位置
|
|
|
if (x < 0 || x >= 3 || y < 0 || y >= 3) continue; // 出界
|
|
|
|
|
|
string v = t;
|
|
|
swap(v[x * 3 + y], v[k]); // x与目标位置交换一下
|
|
|
if (!dist.count(v)) { // 如果t字符串出现过，注意C++取unorderd_map是否存在元素时，需要用count
|
|
|
dist[v] = d + 1; // 记录是上一个距离+1得到的
|
|
|
q.push(v); // 新位置进入队列
|
|
|
pre[v] = {op[i], t}; // 记录v这个字符串的前驱字符串是t，并且，是通过操作符op[i]转化而来
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
// 原始输入是用的一个字符一个空格的形式，无法使用string进行读入
|
|
|
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; // 保证不是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();
|
|
|
|
|
|
return 0;
|
|
|
}
|
