NOIP2002提高组-字串变换

大榕树 \ 信息学奥赛 \ 解题报告

NOIP2002提高组-字串变换

原文链接：http://www.mydrs.org/program/list.asp?id=469

[问题描述]:

　　已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）:
　　　　　A1$ -> B1$
　　　　　A2$ -> B2$
　　规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ …。
　　　　例如：A$＝'abcd'　B$＝'xyz'
　　变换规则为：
　　　　‘abc’->‘xu’　‘ud’->‘y’　‘y’->‘yz’
　　则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：
　　　‘abcd’->‘xud’->‘xy’->‘xyz’
　　共进行了三次变换，使得 A$ 变换为B$。

[输入]:

　　键盘输人文件名。文件格式如下：
　　　A$ B$
　　　A1$ B1$ \
　　　A2$ B2$ |-> 变换规则
　　　... ... /
　　所有字符串长度的上限为 20。

[输出]:

　　输出至屏幕。格式如下：
　　若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"
[输入输出样例]
b.in:
　abcd xyz
　abc xu
　ud y
　y yz

屏幕显示：
　3

分析：

本题是典型的广度优先搜索的例子，但如果只采用正向搜索，某些情况下计算量过大，速度过慢，故采取双向搜索且判重并适当剪枝，效果较好。

程序清单

{$A-,B-,D-,E-,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X-,Y-}
{$M 8192,0,655360}
program NOIPG2;
const maxn=2300;
type
    node=record{定义节点数据类型}
           str:string[115];dep:byte;
         end; {str表示字串，其长度不会超过115（长度超过115的字串
     不可能通过变换成为目标字串，因为题目限定变换10次之内，且串长
     不超过20，即起始串最多可经过5次变换时增长，中间串的最大长度
     为20+5*19=115，否则经过余下的步数不可能变为长度不超过20的
     目标串），dep表示深度}
    ctype=array[1..maxn]of ^node;
    bin=0..1;
var
    maxk:byte;c:array [0..1]of ctype;
    x0:array[0..6,0..1]of string[20];
    filename:string;
    open,closed:array [0..1] of integer;
procedure Init;{读取数据，初始化}
    var f:text;temp:string;i,j:integer;
    begin
      for i:=0 to 1 do
        for j:=1 to maxn do new(c[i,j]);
      write('Input filename:');readln(filename);
      assign(f,filename);reset(f);i:=0;
      while not eof(f) and (i<=6) do begin
        readln(f,temp);
        x0[i,0]:=copy(temp,1,pos(' ',temp)-1);
        x0[i,1]:=copy(temp,pos(' ',temp)+1,length(temp));
        inc(i);
      end;
      maxk:=i-1;close(f);
    end;
procedure calc;
    var i,j,k:integer;st:bin;
        d:string;f:text;
    procedure bool(st:bin);{判断是否到达目标状态或双向搜索相遇}
      var i:integer;
      begin
        if x0[0,1-st]=c[st,closed[st]]^.str then begin
          {如果到达目标状态，则输出结果，退出}
          writeln(c[st,closed[st]]^.dep);
          halt;
        end;
        for i:=1 to closed[1-st] do
          if c[st,closed[st]]^.str=c[1-st,i]^.str then begin
            {如果双向搜索相遇（即得到同一节点），
             则输出结果（2个方向搜索的步数之和），退出}
            writeln(c[st,closed[st]]^.dep+c[1-st,i]^.dep);
            halt;
          end;
      end;
    procedure checkup(st:bin);{判断节点是否与前面重复}
      var i:integer;
      begin
        for i:=1 to closed[st]-1 do
          if c[st,i]^.str=c[st,closed[st]]^.str then begin
            dec(closed[st]);exit;{如果节点重复，则删除本节点}
          end;
        bool(st);{如果节点不重复，再判断是否到达目标状态}
      end;
    procedure expand(st:bin);{扩展产生新节点}
      var i,j,k,lx,ld:integer;
      begin
        inc(open[st]);d:=c[st,open[st]]^.str;{队首节点出队}
        k:=c[st,open[st]]^.dep;ld:=length(d);
        for i:=1 to maxk do begin
          {从队首节点（父节点）出发产生新节点（子节点）}
          lx:=length(x0[i,st]);
          for j:=1 to ld do begin
            if (copy(d,j,lx)=x0[i,st]) and (length(copy(d,1,j-1)+x0[i,1-st]
               +copy(d,j+lx,ld))<=115) then begin
            {如果新节点的串长超过115，则不扩展！即剪掉此枝}
              if closed[st]>=maxn then exit;{如果队列已满，只好退出}
              inc(closed[st]);{新节点入队}
c[st,closed[st]]^.str:=copy(d,1,j-1)+x0[i,1-st]+copy(d,j+lx,ld);
              c[st,closed[st]]^.dep:=k+1;{子节点深度=父节点深度+1}
              checkup(st);{检查新节点是否重复}
            end;
          end;
        end;
      end;
    Begin
      for st:=0 to 1 do begin{正向(st=0)逆向(st=1)搜索节点队列初始化}
        open[st]:=0;closed[st]:=1;
        c[st,closed[st]]^.str:=x0[0,st];c[st,closed[st]]^.dep:=0;
        bool(st);
      end;
      repeat
        {选择节点数较少且队列未空、未满、深度未达到10的方向先扩展}
        if (open[0]<=open[1]) and not ((open[0]>=closed[0]) or
          (closed[0]>=maxn) or (c[0,closed[0]]^.dep>10)) then expand(0);
        if (open[1]<=open[0]) and not ((open[1]>=closed[1]) or
          (closed[1]>=maxn) or (c[1,closed[1]]^.dep>10)) then expand(1);
       {如果一方搜索终止，继续另一方的搜索，直到两个方向都终止}
       if not ((open[0]>=closed[0]) or (closed[0]>=maxn) or
          (c[0,closed[0]]^.dep>10)) then expand(0);
        if not ((open[1]>=closed[1]) or (closed[1]>=maxn) or
          (c[1,closed[1]]^.dep>10)) then expand(1);
      until (open[0]>=closed[0]) or (c[0,closed[0]]^.dep>10) or (closed[0]>=maxn)
          and (closed[1]>=maxn) or (open[1]>=closed[1]) or (c[1,closed[1]]^.dep>10);
       {终止条件：任一方队空（无解）或搜索深度超过10（10步内无解）
        或双方均溢出（可能有解也可能无解，应尽量避免，要尽量把节
        点数组开大一点，采用双向搜索，采取剪枝措施等）}
    End;
BEGIN
    init; calc; writeln('NO ANSWER!')
END.
点评：基本题（较难）考察队列、（双向）广度优先搜索算法及字符串的运算，基本上可以考察出参赛者的数据结构和算法水平。

作者：湖北伍先军
来源：
时间：2003-03-01

上一篇：第八届分区联赛一等奖地区分布
下一篇：USACO三月竞赛橙色题目