You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
76 lines
1.9 KiB
76 lines
1.9 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
struct Node {
|
|
string s;
|
|
int step;
|
|
int k; //'x'在第k位
|
|
};
|
|
|
|
int dx[] = {-1, 0, 1, 0};
|
|
int dy[] = {0, -1, 0, 1};
|
|
|
|
int fact[9];
|
|
bool st[362880];
|
|
|
|
int cantor(string s) { // 求长度为9的字符串某种排列的哈希值
|
|
int x = 0;
|
|
for (int i = 0; i < 9; i++) {
|
|
int smaller = 0;
|
|
for (int j = 0; j < i; j++)
|
|
if (s[j] > s[i]) smaller++; // 求s[i]与其前面的字符组成的逆序对个数
|
|
x += smaller * fact[i];
|
|
}
|
|
return x;
|
|
}
|
|
|
|
int bfs(Node u) {
|
|
st[cantor(u.s)] = 1;
|
|
queue<Node> q;
|
|
q.push(u);
|
|
|
|
while (q.size()) {
|
|
u = q.front();
|
|
q.pop();
|
|
if (u.s == "12345678x") return u.step;
|
|
|
|
int x = u.k / 3; //'x'的行数
|
|
int y = u.k % 3; //'x'的列数
|
|
Node v;
|
|
v.step = u.step + 1;
|
|
for (int i = 0; i < 4; i++) {
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
if (tx < 0 || tx > 2 || ty < 0 || ty > 2) continue;
|
|
// 求出'x'在字符串中的的新位置
|
|
v.k = tx * 3 + ty;
|
|
// 新串长什么样子
|
|
v.s = u.s; // 先抄过来
|
|
v.s[u.k] = u.s[v.k]; // 先用即将和'x'交换的字符覆盖'x'之前的位置
|
|
v.s[v.k] = 'x'; // 再给'x'的新位置赋值'x'
|
|
// 新串的hash值
|
|
int hash = cantor(v.s);
|
|
if (!st[hash]) {
|
|
st[hash] = 1;
|
|
q.push(v);
|
|
}
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
int main() {
|
|
// 预处理fact[i] = i!
|
|
fact[0] = 1;
|
|
for (int i = 1; i < 9; i++) fact[i] = fact[i - 1] * i;
|
|
|
|
char c;
|
|
Node start;
|
|
for (int i = 0; i < 9; i++) {
|
|
cin >> c;
|
|
if (c == 'x') start.k = i;
|
|
start.s.push_back(c);
|
|
}
|
|
start.step = 0;
|
|
printf("%d", bfs(start));
|
|
return 0;
|
|
} |