简要题意：
给定一个 (3 imes 3) 的矩阵，每次可以把空格旁边（四方向）的一个位置移到空格上。求到目标状态的最小步数。
前置知识：
( ext{OK})，现在我们来考虑双向宽搜。
假设 (A) 和 (B) 两个人被困在了迷宫的两个角落，现在他们首先要互相找到对方；他们都会分身术。你认为下面哪一种方法最快：
-
(A) 主动分身去各个路口分支找 (B)，(B) 原地待命。
-
(B) 主动分身去各个路口分支找 (A)，(A) 原地待命。
-
(A) 和 (B) 同时分身去各个路口分支找对方。
无可厚非是最后一种方法最快。但请不要误解：现实生活中我们提倡前两种方案，因为现实中没有人会分身的。
诚然，互相找的效率是最高的。可是你可能会问了：
假设一共 (4) 步找到对方，两人各走 (2) 步和一个人找 (4) 步不是一样的吗？
粗想一下，确实如此。但是在 爆炸性指数级的压力 之下，完全不同。
就在这个问题的基础上，假设每走 (1) 步都有 (4) 种选法（即四方向）。
那么，一个人找的时间是 (4^4 = 256).
两个人同时找对方的时间是 (4^2 + 4^2 = 32).
数据说明，快了 (8) 倍。这单是 (4) 步就快了 (8) 倍！
经过粗略的计算，假设一共要走 (20) 步的话，双向找比单向快 (524288) 倍，约 (5.2 imes 10^5)，假设时间限制是 (1s) 的话，显然这两个程序的分数是有着极大差异的！
这是因为，双向搜索在本质上把步数减半了，而 在指数上减半会让幂大大降低，因此双向搜索会更快。
那么双向搜索适用于哪些题目呢？
- 明确知道起点和终点的。比方说这种题（现编的）：
对于已知的一个数，每次可以将其连续 k 个数字同时 +1.
求让它至少有 p 位连续相同的步数。
显然，终点不明确，无法搜索。你不可能把所有的终点都枚举一遍。
- 明确知道搜索深度的。即明确知道多少步会走到。比方说 埃及分数：
将一个分数分解为若干分数的和。有一些分母不能使用。
显然，你不知道会分解成多少个分数。因此本题需要使用 迭代加深搜索（IDDFS） 而非 ( ext{bfs}).
然后，那你会问了：八数码这一题，我也不知道最多会有多少步呀？
-
那么，你不会自己随机造吗？
-
我怎么造啊？
-
用随机种子搞一个 (0) ~ (8) 的任意排列，然后取出最大答案啊
-
我连 ( ext{std}) 都不会写啊
哦！对。本题你可以稍微分析一下，你会发现，既然肯定能走到，你的直觉：一定不超过 (30) 步。（事实如此）
双向宽搜如何实现呢？
-
将起点和终点一起入队，用 ( ext{vis}) 记录是否访问过。起点拓展的状态 (vis = 1)，终点拓展的状态 (vis = 2)，否则 (vis = 0). 并用 (ans) 记录当前的步数。
-
对当前状态 (u)，转为矩阵并进行四方向的转移，形成新的状态 (v)。
-
若当前状态已搜过，分情况：
-
- (vis_u = vis_v)，直接跳过
-
- (vis_u + vis_v = 3)，输出 (ans_u + ans_v)，停止搜索
-
- (vis_v ot = 0)，则 (vis_v gets vis_u , ans_v gets ans_u+1)，入队，继续搜索。
-
接着入队，进行下一轮搜索。
-
重复搜索直到队列为空（当然本题保证不会无解，因此队列不会为空，但严谨地说明一下）或已有答案。
你会注意到 (vis) 和 (ans) 都需要用 ( ext{map})，这无疑让我们多挂了两个 (log). 假设队列的一个 (log)，一共有 (3) 个 (log).（针对入队的状态个数出现了 (3) 个 (log)） 每次取出状态需要变为矩阵，( imes 9).
那么假设一共搜到状态个数是 (n)，那么：
时间复杂度：(mathcal{O}(9n log^3 n)).
这是理论上的硬性分析。这能用最慢点 (10ms)，(31) 个点共 (149ms) 的优秀时间通过，也就说明，(n) 是 (10^3) 级别的。
如果你不信，代入 (n=10^4)，可得：
大概是 (2.4 imes 10^8) ！你觉得这 (10ms) 能跑完？
要是能跑完，那洛谷评测机早成 神威 · 太湖之光了，(1s) 那就能跑 (2.4 imes 10^{10}) 了，那还不乱套了，(mathcal{O}(n^2)) 都可以稳过 (10^5) 了！
然而实际，时间复杂度：(mathcal{O}( ext{wys})).
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
int n,end=123804765,a[4][4];
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
queue<int> q;
map<int,int> vis,ans;
inline void bfs() {
if(n==end) {puts("0");return;}
q.push(n); q.push(end);
ans[n]=0; ans[end]=1;
vis[n]=1; vis[end]=2; //初始化
while(!q.empty()) {
int now=q.front(),fx,fy; q.pop();
int t=now; /*printf("%d
",now);*/
for(int i=3;i>=1;i--) for(int j=3;j>=1;j--) {
a[i][j]=now%10,now/=10;
if(!a[i][j]) fx=i,fy=j; //转化为矩阵
} for(int i=0;i<4;i++) {
int nx=fx+dx[i],ny=fy+dy[i];
if(nx<1 || nx>3 || ny<1 || ny>3) continue;
swap(a[fx][fy],a[nx][ny]); now=0;
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++) now=now*10+a[j][k]; //再转回来
if(vis[now]==vis[t]) { //搜过
swap(a[fx][fy],a[nx][ny]); //换回来
continue;
} if(vis[now]+vis[t]==3) {
printf("%d
",ans[t]+ans[now]); //记录答案
return;
} ans[now]=ans[t]+1; vis[now]=vis[t];
q.push(now); swap(a[fx][fy],a[nx][ny]); //入队，记录，换回
}
}
}
int main() {
n=read(); bfs();
return 0;
}