CV1018单词接龙
题目描述 Description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at和atide间不能相连。
输入描述 Input Description
输入的第一行为一个单独的整数n(n<=20)表示单词数,以下n行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述 Output Description
只需输出以此字母开头的最长的“龙”的长度
样例输入 Sample Input
5
at
touch
cheat
choose
tact
a
样例输出 Sample Output
23
数据范围及提示 Data Size & Hint
(连成的“龙”为atoucheatactactouchoose)
单词接龙
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n; char a[40][1000]; char kai[2]; bool visit[21]; int ans=0; int judge(char c[],char d[]) { bool pan=true;; int p=strlen(d)-1; for(int i=strlen(c)-1;i>=0&&strlen(c)-i<strlen(d);i--) { if(c[i]==d[0]) { pan=false; for(int j=i+1,q=1;j<=strlen(c)-1;j++,q++) if(c[j]!=d[q]) { pan=true; break; } } if(pan==false) { return strlen(d)-(strlen(c)-i); } } return 0; } void dfs(char b[],int maxn) { int q; ans=max(maxn,ans); for(int i=1;i<=2*n;i++) { if(!visit[i]) { int y=judge(b,a[i]); if(y) { visit[i]=true; dfs(a[i],maxn+y); visit[i]=false; } } } } int main() { scanf("%d",&n); for(int i=1;i<=2*n;i++) { scanf("%s",a[i]); for(int j=0;j<=strlen(a[i])-1;j++) a[i+1][j]=a[i][j]; i++; } scanf("%s",kai); for(int i=1;i<=2*n;i++) { visit[i]=true; if(a[i][0]==kai[0]) dfs(a[i],strlen(a[i])); visit[i]=false; } printf("%d",ans); }