题目描述

小明完成了这样一个数字生成游戏，对于一个不包含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]

输入

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

输出

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

思路

bfs求出所有可能做到的数，将次数记录下来，读入时直接输出
（看起来容易做起来难系列）

var
  t,f:array[0..100000] of longint;
  i,j,k,s,n,m,o:longint;
procedure bfs;
var
  tail,head,l,len,x,xx:longint;
  st:string;
  ch:char;
begin
  f[o]:=1;
  head:=0; tail:=1;
  t[1]:=o;
  str(o,st);
  xx:=length(st);
  while head<=tail do
    begin
      inc(head);
      for i:=1 to 3 do
        begin
          if i=1 then
            begin
              str(t[head],st);
              len:=length(st);
              for j:=1 to len do
                for k:=1 to len do
                  if j<>k then
                    begin
                      ch:=st[j];
                      st[j]:=st[k];
                      st[k]:=ch;
                      val(st,x);
                      if f[x]=0 then
                        begin
                          f[x]:=f[t[head]]+1;
                          inc(tail);
                          t[tail]:=x;
                        end;
                      str(t[head],st);
                    end;
            end;
          if i=2 then
            begin
              str(t[head],st);
              len:=length(st);
              for j:=1 to len do
                begin
                  delete(st,j,1);
                  val(st,x);
                  if f[x]=0 then
                    begin
                      f[x]:=f[t[head]]+1;
                      inc(tail);
                      t[tail]:=x;
                    end;
                  str(t[head],st);
                end;
            end;
          if i=3 then
            begin
              str(t[head],st);
              len:=length(st);
              if len>=xx then continue;
              for j:=1 to len-1 do
                begin
                  for k:=ord(st[j])-48+1 to ord(st[j+1])-48-1 do
                    begin
                      ch:=chr(k+48);
                      insert(ch,st,j+1);
                      val(st,x);
                      if f[x]=0 then
                        begin
                          f[x]:=f[t[head]]+1;
                          inc(tail);
                          t[tail]:=x;
                        end;
                      str(t[head],st);
                    end;
                end;
            end;
        end;
    end;
end;
begin
  readln(o);
  readln(n);
  bfs;
  for i:=1 to n do
    begin
      readln(m);
      if f[m]-1<>0 then writeln(f[m]-1)
      else if o=m then writeln(0)
        else writeln(-1);
    end;
end.