题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述:
输入的第一行为一个单独的整数n(n ≤ 20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述:
只需输出以此字母开头的最长的“龙”的长度
示例1
输入
5
at
touch
cheat
choose
tact
a
输出
23
说明
连成的“龙”为atoucheatactactouchoose
思路：首先题目固定了 “龙”的开头字母，还有条件是每个单词最多用两次，
由于 n <=20 ，所以我们可以直接暴力dfs解决，另外要注意的地方，
就是两个单词可能有多种连接方式，要选择最短前缀、后缀连接，
例如 1 3 2 3 和 3 2 3 1 ，连接为 1 3 2 3 2 3 1 ，而不是 1 3 2 3 1 。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<map>
7 #include<set>
8 #include<vector>
9 #include<queue>
10 #include<list>
11 #include<stack>
12 //#include<unordered_map>
13 using namespace std;
14 #define ll long long
15 const int mod=1e9+7;
16 const int inf=1e9+7;
17 //const int maxn=
18
19 int n;
20
21 map<string,int>book;
22
23 string str[25];
24
25 string t;//存拼接好的字符串字符串
26
27 int maxx;
28
29 inline bool check(string str1,string str2)
30 {
31 int len;//处理到短的字符串长度
32
33 if(str1.size()<str2.size())
34 len=str1.size();
35 else
36 len=str2.size();
37
38 string t1,t2;
39
40 for(int i=1;i<=len-1;i++)//从1开始到len-1检查是否有相同前缀
41 { //不能到len，因为到len等于重合，包含关系，不成立
42 t1=str1.substr(str1.size()-i,i);//截出前串的后缀
43 t2=str2.substr(0,i);//截出后串的前缀
44
45 if(t1==t2)//可以拼接
46 {
47 t=str1.substr(0,str1.size()-i);//截出前串的前一部分
48
49 t+=str2;//拼接 ，存下拼接好的字符串字符串
50
51 return true;
52 }
53 }
54
55 return false;
56 }
57
58 void dfs(string now)
59 {
60 if((int)now.size()>maxx)//刷新最值
61 {
62 maxx=now.size();
63 }
64
65 for(int i=0;i<n;i++)
66 {
67 if(book[str[i]]<2)
68 {
69 if(check(now,str[i])==true)//now后面可以接str[i]
70 {
71 book[str[i]]++;
72 dfs(t);//直接用已经拼接好的t串
73 book[str[i]]--;
74 }
75 }
76 }
77
78 return ;
79 }
80
81 int main()
82 {
83 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
84
85 cin>>n;
86
87 for(int i=0;i<n;i++)
88 cin>>str[i];
89
90 char startt;
91 cin>>startt;//龙头23333
92
93 maxx=-1;//初始化最值
94
95 book.clear();
96
97 for(int i=0;i<n;i++)
98 {
99 if(book[str[i]]<2&&str[i][0]==startt)//符合条件开始dfs
100 {
101 book[str[i]]++;
102
103 dfs(str[i]);
104
105 book[str[i]]--;
106 }
107 }
108
109 cout<<maxx<<endl;
110
111 return 0;
112 }