haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

单词接龙

发布时间:2013-12-18 11:35:57  

单词接龙

问题描述 :

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at和atide间不能相连。

输入文件dcjr.in:

输入的第一行为一个单独的整数n(n<=20)表示单词数,以下n行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出文件dcjr.out:

一个整数,只需输出以此字母开头的最长的“龙”的长度.

样例:

输入

5

at

touch

cheat

choose

tact

a

输出

23(连成的“龙”为atoucheatactactouchoose)

参考程序:

const

maxn=20;

var

s:array[1..maxn] of string;

head:char;

best,i,n:integer;

add:array[1..maxn,1..maxn] of integer;

used:array[1..maxn] of integer;

procedure calcadd;

var

i,j,k,t,min:integer;

ok:boolean;

begin

for i:=1 to n do

for j:=1 to n do

begin

if length(s[i])<length(s[j]) then min:=length(s[i])

else min:=length(s[j]);

for k:=1 to min-1 do

begin

{check}

ok:=true;

for t:=1 to k do

if s[j,t]<>s[i,length(s[i])-k+t] then

begin

ok:=false;

break;

end;

if ok then break;

end;

if ok then

add[i,j]:=length(s[j])-k else

add[i,j]:=0;

end;

end;

procedure search(last,len:integer); var

i:integer;

begin

if len>best then

best:=len;

for i:=1 to n do

if (add[last,i]>0)and(used[i]<2) then begin

inc(used[i]);

search(i,len+add[last,i]); dec(used[i]);

end;

end;

begin

assign(input,'dcjr.in');reset(input); assign(output,'dcjr.out');

rewrite(output);

readln(n);

for i:=1 to n do

readln(s[i]);

readln(head);

calcadd;

best:=0;

fillchar(used,sizeof(used),0); for i:=1 to n do

if s[i,1]=head then

begin

used[i]:=1;

search(i,length(s[i])); used[i]:=0;

end;

writeln(best);

close(input);

close(output);

end.

上一篇:回文数
下一篇:砝码称重
网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com