|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
typedef unordered_map<string, int> MSI;
|
|
|
string st, ed = "12345678x";
|
|
|
|
|
|
int dx[] = {-1, 0, 1, 0};
|
|
|
int dy[] = {0, 1, 0, -1};
|
|
|
|
|
|
// AC掉AcWing 845, 运行时间：1440 ms
|
|
|
int extend(queue<string> &qa, MSI &da, MSI &db) {
|
|
|
string t = qa.front();
|
|
|
qa.pop();
|
|
|
|
|
|
int k = t.find('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 > 2 || y < 0 || y > 2) continue;
|
|
|
string v = t;
|
|
|
swap(v[k], v[x * 3 + y]);
|
|
|
if (da[v]) continue;
|
|
|
if (db[v]) return da[t] + 1 + db[v];
|
|
|
da[v] = da[t] + 1;
|
|
|
qa.push(v);
|
|
|
}
|
|
|
return -1;
|
|
|
}
|
|
|
|
|
|
int bfs() {
|
|
|
//不加特判挂一个点
|
|
|
if (st == ed) return 0;
|
|
|
|
|
|
//双队列
|
|
|
queue<string> qa, qb;
|
|
|
//双距离
|
|
|
MSI da, db;
|
|
|
|
|
|
//将起点放入队列
|
|
|
qa.push(st);
|
|
|
da[st] = 0;
|
|
|
|
|
|
//将终点放入队列
|
|
|
qb.push(ed);
|
|
|
db[ed] = 0;
|
|
|
|
|
|
int t;
|
|
|
//两个队列均不空
|
|
|
while (qa.size() && qb.size()) {
|
|
|
//双队列优化策略：哪个小就优先拓展哪个
|
|
|
if (qa.size() <= qb.size())
|
|
|
t = extend(qa, da, db);
|
|
|
else
|
|
|
t = extend(qb, db, da);
|
|
|
if (t > 0) break;
|
|
|
}
|
|
|
return t; //返回最短距离
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
//加快读入
|
|
|
cin.tie(0), ios::sync_with_stdio(false);
|
|
|
|
|
|
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++;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
//奇数个逆序对输出-1
|
|
|
if (nums & 1)
|
|
|
puts("-1");
|
|
|
else
|
|
|
//输出最短距离
|
|
|
printf("%d\n", bfs());
|
|
|
|
|
|
return 0;
|
|
|
} |
