这个是map双向搜索，函数名有点草率别介意
awa \(owo)/ ~~膜拜大佬~~
by smallcandy @ 2024-01-29 19:59:16
标准代码：
```cpp
#include <iostream>
#include <map>
#include <queue>
using namespace std;
int bg, ed = 123804765;
int a[10];
// 1表示从最终状态开始的搜索
// 0表示从开始状态开始的搜索
map<int, int> rec[2];
queue<pair<int, bool> > Q;
// 修改状态，op表示状态的方式
int change(int x, int op)
{
int p; // 记录0所在的位置
// 将状态解开
for (int i = 9; i; i--) {
a[i] = x % 10;
x /= 10;
if (a[i] == 0)
p = i;
}
switch (op)
{
case 1: // 向上移动
if (p <= 3) return -1;
swap(a[p], a[p-3]);
break;
case 2: // 向下移动
if (p >= 7) return -1;
swap(a[p], a[p+3]);
break;
case 3: // 向左移动
if ((p % 3) == 1) return -1;
swap(a[p], a[p - 1]);
break;
case 4: // 向右移动
if ((p % 3) == 0) return -1;
swap(a[p], a[p + 1]);
break;
default:
break;
}
x = 0;
for (int i = 1; i <= 9; i++)
x = x * 10 + a[i];
return x;
}
void check(int x, pair<int , bool> h)
{
if (x != -1) {
if (rec[h.second ^ 1].count(x) == true) {
cout << rec[h.second ^ 1][x] + rec[h.second][h.first] + 1 << endl;
exit(0);
}
else {
rec[h.second][x] = rec[h.second][h.first] + 1;
Q.push(make_pair(x, h.second));
}
}
}
int main()
{
cin >> bg;
if (bg == ed) {
cout << 0;
return 0;
}
Q.push(make_pair(bg, 0));
Q.push(make_pair(ed,1));
while (!Q.empty()) {
pair<int, bool> h = Q.front();
Q.pop();
int x = change(h.first, 1);
check(x, h);
x = change(h.first, 2);
check(x, h);
x = change(h.first, 3);
check(x, h);
x = change(h.first, 4);
check(x, h);
}
return 0;
}
```
参考参考
by __zyy_wgcs__ @ 2024-01-30 10:05:14