显然判重可以用map,然而map太慢了.于是我就用bitset,开九亿似乎不会炸,然而蜜汁ce,然后开八位算了,最后一位直接扔掉
而且这样跑得很快.
本来打算直接在一个9位数上模来模去搞一下然后四个方向太麻烦了所以干脆拆开交换再合起来入队
```cpp
#include<bits/stdc++.h>
using namespace std;
long long T;
long long n;
bitset<90000000> Map;
struct node
{
long long a;
long long d;//存0的位置
long long s;//记录步数
};
queue<node> q;
node u,v;
long long a[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
long long b[10];
inline void rpk()
{
b[1]=0;
for (long long i=1;i<=9;i++)
{
b[9-i+1]=v.a%10;
v.a/=10;
}//拆成9位
long long t=b[u.d];b[u.d]=b[v.d];b[v.d]=t;//交换
v.a=0;
for (long long i=1;i<=9;i++)
{
v.a+=b[i]*a[9-i];
}//再拼起来
if (Map[v.a/10]==0) q.push(v);
Map[v.a/10]=1;
}
int main()
{
scanf("%lld",&n);
u.a=n;
for (long long i=1;i<=9;i++)
{
if ((n%10)==0)
{
u.d=9-i+1;
//cout<<u.d;
break;
}
n/=10;
}
Map[n/10]=1;//起点标记
T=123804765;
u.s=0;
q.push(u);
while (!q.empty())
{
u=q.front();q.pop();
if (u.d>3)//不在第一行
{
v.d=u.d-3;//改变0的位置
v.a=u.a;
v.s=u.s+1;
rpk();
if (v.a==T)
{
printf("%lld",u.s+1);
return 0;
}
}//上移
if (u.d<7)//不是最下面的几行
{
v.d=u.d+3;
v.a=u.a;
v.s=u.s+1;
rpk();
if (v.a==T)
{
printf("%lld",u.s+1);
return 0;
}
}下移
if ((u.d%3==1)||(u.d%3==2))//不是最后一列就可以左移
{
v.d=u.d+1;
v.a=u.a;
v.s=u.s+1;
rpk();
if (v.a==T)
{
printf("%lld",u.s+1);
return 0;
}
}//左移
if (u.d%3!=1)//不在第一列就可以右移
{
v.d=u.d-1;
v.a=u.a;
v.s=u.s+1;
rpk();
if (v.a==T)
{
printf("%lld",u.s+1);
return 0;
}
//cout<<v.a<<"\n";
}//右移
}
return 0;
}
```