题目描述
小明完成了这样一个数字生成游戏，对于一个不包含00的数字ss来说，有以下33种生成新的数的规则：
-
将ss的任意两位对换生成新的数字，例如143143可以生成314,413,134314,413,134；
-
将ss的任意一位删除生成新的数字，例如143143可以生成14,13,4314,13,43
-
在ss的相邻两位之间s_i,s_{i + 1}si,si+1之间插入一个数字x，x需要满足s_i<x<s_{i + 1}si<x<si+1。例如143143可以生成1243,13431243,1343，但是不能生成1143,15431143,1543等。
现在小明想知道，在这个生成法则下，从ss开始，每次生成一个数，可以用然后用新生成的数生成另外一个数，不断生成直到生成tt至少需要多少次生成操作。
另外，小明给规则33又加了一个限制，即生成数的位数不能超过初始数ss的位数。若ss是143143，那么12431243与13431343都是无法生成的；若ss为14431443，那么可以将ss删除变为143143，再生成12431243或13431343。
输入输出格式
输入格式：
第一行包含11个正整数，为初始数字ss。
第二行包含一个正整数mm，为询问个数。
接下来mm行，每行一个整数tt（tt不包含00），表示询问从ss开始不断生成数字到tt最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字ss。
输出格式：
共mm行，每行一个正整数，对每个询问输出最少操作数，如果无论如果无论也变换不成，则输出-1−1。
输入输出样例
输入样例#1： 复制
143
3
134
133
32
输出样例#1： 复制
1
-1
4
说明
143143 ->134134
133133无法得到
143143 -> 1313 -> 123123 ->2323->3232
对于20%20%的数据，s < 100s<100；
对于40%40%的数据，s < 1000s<1000；
对于40%40%的数据，m < 10m<10；
对于60%60%的数据，s < 10000s<10000；
对于100%100%的数据，s < 100000,m ≤ 50000s<100000,m≤50000。
爆搜
没了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
using namespace std;
queue <int>q;
int i,m,n,j,k,a[2000011],b[2000011],s,f[10001],sdf,cnt;
int zh(int *a,int k)
{
int ans=0;
for(int i=k;i>=1;i--)ans=ans*10+a[i];
cnt+=1;
return ans;
}
void bfs()
{
b[s]=1;
q.push(s);
while(q.size())
{
int s=q.front(); q.pop();
int k=s,l=0;
while(k) l+=1,f[l]=k%10,k/=10;
for(int k=s,i=1,d=10;i<=l;i++,d*=10)
{
int t=k/d*d/10, x=k%(d/10);
int y=t+x;
if(!b[y]) b[y]=1, a[y]=a[s]+1, q.push(y);
}
if(l!=n)
{
for(int k=s,i=1,d=10;i<l;i++,d*=10)
{
int t=k/d, x=k%d, z=k/d%10; int y=k%d/(d/10);
for(int j=z+1; j<y;j++)
{
int r=t*d*10+j*d+x;
if(!b[r]) b[r]=1, a[r]=a[s]+1, q.push(r);
}
}
}
for(int i=1;i<=l;i++)
for(int j=1;j<=l;j++)
{
if(f[i]==f[j]) continue;
swap(f[i],f[j]);
int r=zh(f,l);
if(!b[r]) b[r]=1, a[r]=a[s]+1, q.push(r);
swap(f[i],f[j]);
}
}
}
int main()
{
scanf("%d",&s);
k=s; while(k) k/=10, n+=1;
bfs();
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d",&k);
if(!b[k]) printf("-1
");
else printf("%d
",a[k]);
}
}