Description
小明完成了这样一个数字生成游戏，对于一个不包含0的数字s来说，有以下3种生成新的数的规则： 1.将s的任意两位对换生成新的数字，例如143可以生成341，413，134； 2.将s的任意一位删除生成新的数字，例如143可以生成14，13，43 3.在s的相邻两位之间s[i]，s[i + 1]之间插入一个数字x，x需要满足s[i]<x<s[i + 1]，即比它插入位置两边的数小。例如143可以生成1243，1343，但是不能生成1143，1543等。 现在小明想知道，在这个生成法则下，从s开始，每次生成一个数，可以用新生成的数生成另外一个数，不断生成直到生成t至少需要多少次生成操作。 另外，小明给规则3又加了一个限制，即生成数的位数不能超过初始数s的位数。若s是143，那么1243与1343都是无法生成的；若s为1443，那么可以将s删除4变为143，再生成1243或1343。Input
输入文件gen.in的第一行包含1个正整数，为初始数字s。 第2行包含一个正整数m，为询问个数。 接下来m行，每行一个整数t（t不包含0），表示询问从s开始不断生成数字到t最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字s。
Output
输出文件gen.out包括m行，每行一个正整数，对每个询问输出最少操作数，如果无论也变换不成，则输出-1。Sample Input
143 3 134 133 32
Sample Output
1 -1 4
Data Constraint
【样例说明】 143->134 133无法得到 143->13->123->23->32 【数据规模与约定】 对于20%的数据，s<100； 对于40%的数据，s<1000； 对于40%的数据，m<10； 对于60%的数据，s<10000； 对于100%的数据，s<100000，m≤50000。
分析：就是一个超暴力的BFS，一开始把原数的所有可能的答案都搜出来，然后输出需要的就可以了。
代码:
const maxn=100000; maxv=30000; var m,i,n,k:longint; h:array [0..maxn] of longint; procedure bfs; var head,tail,i,j,t,v,c,len:longint; ch,k:char; s1,s:string; list,f:array [1..maxv] of longint; begin head:=0; tail:=1; list[tail]:=n; h[n]:=0; f[tail]:=0; str(list[tail],s); len:=length(s); repeat head:=head mod maxv+1; str(list[head],s); for i:=1 to length(s) do begin for j:=i+1 to length(s) do begin s1:=s; ch:=s1[i]; s1[i]:=s1[j]; s1[j]:=ch; val(s1,v,c); if h[v]=-1 then begin tail:=tail mod maxv+1; f[tail]:=f[head]+1; h[v]:=f[tail]; list[tail]:=v; end; end; end; if length(s)>1 then begin for i:=1 to length(s) do begin s1:=s; delete(s1,i,1); val(s1,v,c); if h[v]=-1 then begin tail:=tail mod maxv+1; f[tail]:=f[head]+1; h[v]:=f[tail]; list[tail]:=v; end; end; end; if length(s)<len then begin for i:=1 to length(s)-1 do begin for k:=s[i] to s[i+1] do if (s[i]<k) and (k<s[i+1]) then begin s1:=copy(s,1,i)+k+copy(s,i+1,length(s)); val(s1,v,c); if h[v]=-1 then begin tail:=tail mod maxv+1; f[tail]:=f[head]+1; h[v]:=f[tail]; list[tail]:=v; end; end; end; end; until head=tail; end; begin {assign(input,'data.in'); assign(output,'data.out'); reset(input); rewrite(output); } readln(n); readln(m); for i:=1 to 100000 do h[i]:=-1; bfs; for i:=1 to m do begin readln(k); writeln(h[k]); end; {close(input); close(output); } end.