表A和表B各含k(k<=20)个元素，元素编号从1到k。两个表中的每个元素都是由0和1组成的字符串。（不是空格）字符串的长度<=20。例如表6-1的A和B两个表，每个都含有3个元素（k=3）。
表6-1
A B
元素编号 1 2 3 字符串 1 10111 10 元素编号 1 2 3 字符串 111 10 0 对于表A和表B，存在一个元素编号的序列2113，分别用表A中的字符串和表B中的字符吕去置换相应的元素编号，可得到相同的字符串序列101111110
输入数据：
输入文件名由键盘输入该文件； 第1 行为k的值；
第二行至第k+1行为表A的（依次是元素编号从1至k的相应0和1字符串）； 第k+2行至第2k+1行为表B的内容（依次是元素编号从1至k的相应0和1字符串）；
输出数据
输出文件名为output.txt，该文件只有一行。或是S(AB)的值，或是’no answer’(无解时)。S(AB)是元素编号序列，输出时各个编号占一行。 （宽搜是求出最短） 程序如下：
const p:string='123456789abcdefghijk'; var a,b:array[1..20] of string[20];
sa,sb:array[0..100000] of string[101]; sc:array[0..100000] of string[20]; k,i,j,x,y,z:longint; f:text;
function can(y:longint):boolean; begin
if (length(sa[y])<=100)and(length(sb[y])<=100)and
((copy(sa[y],1,length(sb[y]))=sb[y])or(copy(sb[y],1,length(sa[y]))=sa[y])) then can:=true else can:=false; end; begin
assign(f,'35.dat'); reset(f); readln(f,k);
for i:=1 to k do readln(f,a[i]); for i:=1 to k do readln(f,b[i]);
close(f); x:=1; sa[1]:=''; sb[1]:=''; sc[1]:=''; y:=2; repeat
for z:=1 to k do begin
sa[y]:=sa[x]+a[z]; sb[y]:=sb[x]+b[z]; sc[y]:=sc[x]+p[z]; if can(y) then
if sa[y]=sb[y] then begin writeln(sc[y]);exit;end else y:=y mod 100000 +1; end;
x:=x mod 100000+1; until x=y; writeln('no'); end.
此题优化：由于sa和sb的头一致，则可以sa, sb只存一个。
宽搜由于要存中间所产生的所有状态，所以存储量特别大。因此把j=j+1改为j:=j mod 100000+1,则可以节省内存。那同时I>=j只能为I=j;这种情况适用于祖先无用的情况。 宽搜浪费在判重上。
双向搜索：从初始状态到目标状态同时搜，相遇时为止，因为宽搜是按层进行，因此一
定会相遇，而且搜索规划是可逆的，就可以使用双向搜索，又因都是从三角的顶点开始，因此可以节省一半的判重。
1、最短编号序列
程序如下：（双向搜索） const
p:string[20]='123456789abcdefghijk'; var
sa,sb,ta,tb:array[1..100000]of string[101]; sc,tc:array[1..100000]of string[20]; a,b:array[1..20]of string[20]; i,j,k,ti,tj,x:longint; f:text;
function can1(k:longint):boolean; begin
can1:=(length(sa[k])<=100)and(length(sb[k])<=100)and((pos(sb[k],sa[k])=1)or(pos(sa[k]
,sb[k])=1));
end;
function can2(k:longint):boolean; begin
can2:=(length(ta[k])<=100)and(length(tb[k])<=100)and
((copy(tb[k],length(tb[k])-length(ta[k])+1,length(ta[k]))=ta[k])or (copy(ta[k],length(ta[k])-length(tb[k])+1,length(tb[k]))=tb[k])); end;
procedure result1(j:integer); var
x:integer; begin
for x:=ti to tj-1 do
if sa[j]+ta[x]=sb[j]+tb[x] then begin
writeln(sc[j]+tc[x]); halt; end; end;
procedure result2(tj:integer); var
x:integer; begin
for x:=i to j-1 do
if sa[x]+ta[tj]=sb[x]+tb[tj] then begin
writeln(sc[x]+tc[tj]); halt; end; end; begin
assign(f,'32.dat'); reset(f); readln(f,k);
for i:=1 to k do readln(f,a[i]); for i:=1 to k do readln(f,b[i]); close(f);
sa[1]:='';sb[1]:='';sc[1]:=''; ta[1]:='';tb[1]:='';tc[1]:=''; i:=1; j:=2; ti:=1; tj:=2; repeat
for x:=1 to k do begin
sa[j]:=sa[i]+a[x]; sb[j]:=sb[i]+b[x]; sc[j]:=sc[i]+p[x];
if can1(j) then begin result1(j);j:=j+1;end; end; i:=i+1;
for x:=1 to k do begin
ta[tj]:=a[x]+ta[ti]; tb[tj]:=b[x]+tb[ti]; tc[tj]:=p[x]+tc[ti];
if can2(tj) then begin result2(tj);tj:=tj+1;end; end; ti:=ti+1;
until (i=j)or(ti=tj); writeln('no answer'); end.
二、八数码（双向搜索） type
node=array[1..3,1..3]of 0..8; integer=longint; const
start:node=((2,8,3),(1,6,4),(7,0,5)); goal:node=((1,2,3),(8,0,4),(7,6,5));
rule:array[1..4,1..2]of -1..1=((1,0),(-1,0),(0,1),(0,-1)); var
a,aa:array[1..50000]of node; b,bb:array[1..50000]of longint; i,j,x,y,k,ii,jj,s:integer;
function nrep(k:integer):boolean; var
i,j,l:integer; p:boolean; begin
nrep:=false;
for i:=1 to k-1 do begin p:=true;
for j:=1 to 3 do for l:=1 to 3 do
if a[i,j,l]<>a[k,j,l] then begin p:=false;break;end; if p then exit; end;
nrep:=true; end;
function nrepaa(k:integer):boolean; var
i,j,l:integer; p:boolean; begin
nrepaa:=false; for i:=1 to k-1 do begin p:=true;
for j:=1 to 3 do for l:=1 to 3 do
if aa[i,j,l]<>aa[k,j,l] then begin p:=false;break;end; if p then exit; end;
nrepaa:=true; end;
procedure print(k:integer); var
i,j:integer; begin
if k=0 then exit; print(b[k]); for i:=1 to 3 do begin
for j:=1 to 3 do write(a[k,i,j]:2); writeln; end;
writeln('-----------'); s:=s+1; end;
procedure printaa(k:integer); var
i,j:integer; begin
if k=0 then exit; for i:=1 to 3 do begin
for j:=1 to 3 do write(aa[k,i,j]:2); writeln; end;
writeln('-----------'); s:=s+1;
printaa(bb[k]);