数字生成游戏 纪中2570 bfs

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]

Input

输入文件gen.in的第一行包含1个正整数，为初始数字s。 第2行包含一个正整数m，为询问个数。 接下来m行，每行一个整数t（t不包含0），表示询问从s开始不断生成数字到t最少要进行多少次操作。任两个询问独立，即上一个询问生成过的数到下一个询问都不存在，只剩下初始数字s。

Output

输出文件gen.out包括m行，每行一个正整数，对每个询问输出最少操作数，如果无论也变换不成，则输出-1。

Data Constraint

【数据规模与约定】 对于20%的数据，s<100； 对于40%的数据，s<1000； 对于40%的数据，m<10； 对于60%的数据，s<10000； 对于100%的数据，s<100000，m≤50000。

分析

因为s<100000,所以最多不超过5位数，最多只能产生99999个数。 所以可以用一个桶判断一下有没有产生过这个数，没有就入队。 按照规则来bfs，暴力不会爆。 ps：一开始就可以预处理出s可以推出哪些数，o(1)解出

代码

const maxn=200100; var queue:array[1..maxn] of string; status,f:array[1..maxn] of longint; n,m:longint; long:longint; procedure bfs; var i,j,k:longint; head,tail:longint; long2:longint; s:string; c:char; s1:longint; begin head:=0; tail:=1; status[n]:=1; f[n]:=0; str(n,queue[1]); repeat head:=head+1; val(queue[head],s1); long2:=length(queue[head]); if long2>1 then for i:=1 to long2 do begin s:=queue[head]; delete(s,i,1); val(s,j); if status[j]=0 then begin tail:=tail+1; status[j]:=1; queue[tail]:=s; f[j]:=f[s1]+1; end; end; for i:=1 to long2 do for k:=i+1 to long2 do begin s:=queue[head]; c:=s[i]; insert(c,s,k+1); c:=s[k]; insert(c,s,i+1); delete(s,i,1); delete(s,k,1); val(s,j); if status[j]=0 then begin tail:=tail+1; status[j]:=1; queue[tail]:=s; f[j]:=f[s1]+1; end; end; if long2<long then for i:=1 to long2-1 do begin for k:=ord(queue[head][i])+1 to ord(queue[head][i+1])-1 do begin s:=queue[head]; insert(chr(k),s,i+1); val(s,j); if status[j]=0 then begin tail:=tail+1; status[j]:=1; queue[tail]:=s; f[j]:=f[s1]+1; end; end; end; until head=tail; end; procedure main; var i,j,k:longint; x:longint; begin readln(n); i:=n; long:=0; while i<>0 do begin long:=long+1; i:=i div 10; end; for i:=1 to maxn do f[i]:=maxlongint; bfs; readln(m); for i:=1 to m do begin readln(x); if f[x]=maxlongint then writeln(-1) else writeln(f[x]); end; end; begin main; end.