85 lines
1.9 KiB
C++
85 lines
1.9 KiB
C++
#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;
|
||
} |