题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
输入输出格式
输入格式：
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式：
只需输出以此字母开头的最长的“龙”的长度
输入输出样例
输入样例#1：
5
at
touch
cheat
choose
tact
a
输出样例#1：
23 （连成的“龙”为atoucheatactactouchoose）
这个题可以写出每两个单词之间的所能叠加的长度然后用dfs搜索得到最长的结果
#include <iostream>
#include <string.h>
using namespace std;
char s[33][33];
int len[33][33];
int vis[33];
int n,ans;
void make()
{
char s1[33],s2[33];
int k,minlong;
int flag;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
minlong=min(strlen(s[i]),strlen(s[j]));
flag=1;
k=1;
len[i][j]=0;
while (flag&&k<minlong) {
for(int z=strlen(s[i])-k;z<=strlen(s[i]);z++)
{
s1[z-strlen(s[i])+k]=s[i][z];//拼接的前一半的后半部
}
for(int z=0;z<k;z++)
{
s2[z]=s[j][z];
}
s2[k]=' ';
if(!strcmp(s1, s2))
{
len[i][j]=strlen(s[j])-k;//减去覆盖的
flag=0;
}
else
k++;
}
}
}
}
void tryit(int last,int length)
{
ans=max(ans,length);
for(int i=1;i<=n;i++)
{
if(len[last][i]&&vis[i]<2)
{
vis[i]++;
tryit(i, length+len[last][i]);
vis[i]--;
}
}
}
int main()
{
char ch;
while(cin>>n){
memset(vis, 0, sizeof(vis));
memset(len, 0, sizeof(len));
for(int i=1;i<=n;i++)cin>>s[i];
cin>>ch;
make();
ans=0;
for(int i=1;i<=n;i++)
{
if(s[i][0]==ch)
{
vis[i]=1;
tryit(i, strlen(s[i]));
vis[i]=0;
}
}
cout<<ans<<endl;
}
return 0;
}