单词接龙

2019-11-14 11:01:46

字体：大中小

来源：转载

供稿：网友

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

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

输出格式：只需输出以此字母开头的最长的“龙”的长度

输入输出样例 输入样例#1： 5 at touch cheat choose tact a 输出样例#1： 23 （连成的“龙”为atoucheatactactouchoose）

说明这一题要用到回溯，会简单些。

程序如下：

var a:array[1..20] of string; b,c:array[1..20] of longint; l,n,max:longint; s:string;PRocedure dfs(head:string);var k,j,i:byte; s1,s2:string;begin for i:=1 to n do if c[i]<2 then begin s:=a[i]; if length(head)>=b[i] then k:=b[i]-1 else k:=length(head); s1:=''; s2:=''; for j:=1 to k do begin s1:=head[length(head)+1-j]+s1; s2:=s2+s[j]; if s1=s2 then begin l:=l+b[i]-j; if l>max then max:=l; inc(c[i]); dfs(a[i]); dec(c[i]); l:=l+j-b[i]; end; end; end;end;begin readln(n); for l:=1 to n do begin readln(s); a[l]:=s; b[l]:=length(s); end; readln(s); l:=length(s); dfs(s); writeln(max);end.

上一篇：怎么用循环实现dos框前景色的变换~

下一篇：不得已二 Java两个栈模拟一个队列