记录编号	7231	评测结果	AAAAWAWW
题目名称	[NOIP 2002]字串变换	最终得分	62
用户昵称	王瑞祥K	是否通过	未通过
代码语言	Pascal	运行时间	0.101 s
提交时间	2008-11-07 13:10:34	内存使用	0.61 MiB

program stringp(input,output);
type
 stringtype=string;
var
 queuez,queuef:array[1..1000] of stringtype;
 rule:array[1..6,1..2] of stringtype;
 countz,countf:array[1..1000] of integer;
 start,goal:stringtype;
 hz,hf,tz,tf,rp:integer;
procedure init;
var i,p,j:integer; s:stringtype;
begin
 assign(input,'string.in');assign(output,'string.out');
 reset(input);rewrite(output);
 readln(s);
 p:=pos(' ',s);
 start:=copy(s,1,p-1);
 goal:=copy(s,p+1,length(s));
 i:=0;
 while not eof do
 begin
  inc(i);
  readln(s);
  p:=pos(' ',s);
  rule[i,1]:=copy(s,1,p-1);
  rule[i,2]:=copy(s,p+1,length(s));
 end;
 rp:=i;
 hz:=1;hf:=1;tz:=1;tf:=1;
 queuez[1]:=start;
 queuef[1]:=goal;
 countf[1]:=0;countz[1]:=0;
end;
procedure reverse1(x:integer;t:boolean; var temp:stringtype);
var i:integer;
begin
 t:=false;
 for i:=1 to length(temp)-length(rule[x,1])+1 do
 begin
  if copy(temp,i,length(rule[x,1]))=rule[x,1] then
  begin
   t:=true;
   delete(temp,i,length(rule[x,1]));
   insert(rule[x,2],temp,i);
   exit;
  end;
 end;
end;
procedure reverse2(x:integer;t:boolean; var temp:stringtype);
var i:integer;
begin
 t:=false;
 for i:=1 to length(temp)-length(rule[x,2])+1 do
 begin
  if copy(temp,i,length(rule[x,2]))=rule[x,2] then
  begin
   t:=true;
   delete(temp,i,length(rule[x,2]));
   insert(rule[x,1],temp,i);
   exit;
  end;
 end;
end;
procedure dbfs;
var i,j:integer; temp:stringtype; t,visited:boolean;
begin
 while (tf>=hf)or(tz>=hz) do
 begin
  for i:=1 to 6 do
  begin
   temp:=queuez[hz];
   reverse1(i,t,temp);
   if t then
   begin
    for j:=1 to tf do
    if temp=queuef[j] then
    begin
     writeln(countz[hz]+1+countf[j]);
     exit;
    end;
    visited:=false;
    for j:=1 to tz do
    if temp=queuez[j] then
    begin
     visited:=true;
     break;
    end;
    if not visited then begin
     inc(tz);
     queuez[tz]:=temp;
     countz[tz]:=countz[hz]+1;
     if countz[tz]> 10 then
     begin
      writeln('NO ANSWER!');
      exit;
     end;
    end;
   end;
  end;
  inc(hz);

  for i:=1 to 6 do
  begin
   temp:=queuef[hf];
   reverse2(i,t,temp);
   if t then
   begin
    for j:=1 to tf do
    if temp=queuez[j] then
    begin
     writeln(countf[hf]+1+countz[j]);
     exit;
    end;
    visited:=false;
    for j:=1 to tf do
    if temp=queuef[j] then
    begin
     visited:=true;
     break;
    end;
    if not visited then begin
     inc(tf);
     queuef[tf]:=temp;
     countf[tf]:=countf[hf]+1;
     if countf[tf]> 10 then
     begin
      writeln('NO ANSWER!');
      exit;
     end;
    end;
   end;
  end;
  inc(hf);
 end;
 writeln('NO ANSWER!');
end;
begin
 init;
 dbfs;
 close(input);close(output);
end.