UC知道noip2002 字串变换
来源：百度知道 编辑：UC知道 时间：2024/06/06 20:14:04
[问题描述]:
已知有两个字串 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$ |-> 变换规(guī)则
... ... /
所有字符串长度的上限为 20。
[输出]:
输出至屏幕。格式如下：
若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出"NO ANSWER!"
[输入输出样例]
b.in:
abcd xyz
abc xu
ud y
y yz
屏幕显示：
3
请不要抄,说说基本思路即可,特别是规则的存法,谢谢
请给一个更详细的算法模型,特别是规则存储
广搜
从初始态向目标态搜，同时从目标态向初始态搜。不用双向搜索的判断相遇，也不用hash判重，因为状态不能存。有点慢，但能过。
回复：用一个二维数组存规则，a[i,1]，a[i,2]为一个规则的两个字符串
用广搜，广搜你应该会吧？不会的话就只有学咯，就是简单的搜，不用hash判重
只是从两头同时搜而已
附一个代码吧
var
x,y:string;
a,b:array[1..10] of string;
l,l1:array[1..10] of integer;
t,t1:array[1..100000] of string;
c,c1:array[1..100000] of byte;
i,j,k,n,ans,clo,ope,len,i1,j1,k1,clo1,ope1,len1,m1,m,le,p,q:integer;
s,xx,xx1:string;
flag,flag1,f1,f2:boolean;
procedure bfs;
begin
clo:=0; ope:=1; t[1]:=x; c[1]:=0; clo1:=0; ope1:=1; t1[1]:=y; c1[1]:=0;
flag:=true; flag1:=true;
while (flag)and(flag1) do
begin
if (c[clo+1]<10)and(c[clo+1]<ans)and(clo+1<=ope) then
begin
inc(clo);
len:=length(t[clo]);
for j:=1 to n do
for i:=1 to len-l[j]+1 do
begin