[洛谷][dfs]单词接龙

单词接龙

Description

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如

Input

输入的第一行为一个单独的整数

Output

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

Examples

Input

5
at
touch
cheat
choose
tact
a

Output

正确解法：

两个字符串不能完全覆盖。每个字符串可使用两次。若有多个重复的使用最小的。

如果 allaskask 和 askaskljk 则返回3，而不是6.

首先的难点是找出 s1 和 s2 的重复点。

1 for (int i = 1; i < min(s1.size(), s2.size()); i++)//枚举重复的长度-1
2     {
3         int flag = 1;
4         for (int j = 0; j < i; j++)//看这个长度是否相等
5             if (s1[s1.size() - i + j] != s2[j])
6                 flag = 0;
7         if (flag)    return i;//若相等，直接返回。
8     }
9     return 0;

剩下的就是dfs+回溯。

最后一点是要从给定的字母开头，原本想是字符串的第一个字母是这个字母，可是因为是字符串组，所以很难。

于是我们把这个字母变成 ‘ ’+字母这样就变成了一个长度为2的字符串。但要记住目前最大长度为1.

把这个新构建的字符串扔进去就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<map>
 6 #include<set>
 7 #include<algorithm>
 8 #include<cmath>
 9 using namespace std;
10 int n,book[30],maxx=1;
11 char ch;
12 string s[30];
13 int chongfu(string s1, string s2)
14 {
15     for (int i = 1; i < min(s1.size(), s2.size()); i++)
16     {
17         int flag = 1;
18         for (int j = 0; j < i; j++)
19             if (s1[s1.size() - i + j] != s2[j])
20                 flag = 0;
21         if (flag)    return i;
22     }
23     return 0;
24 }
25 void dfs(string s1,int changdu)
26 {
27     maxx = max(maxx, changdu);
28     for (int i = 1; i <= n; i++)
29     {
30         int c = chongfu(s1, s[i]);
31         if (c > 0 && book[i] < 2)
32         {
33             book[i]++;
34             dfs(s[i],changdu+s[i].size()-c);
35             book[i]--;
36         }
37     }
38     return ;
39 }
40 int main()
41 {
42     scanf("%d",&n);
43     for (int i = 1; i <= n; i++)
44         cin >> s[i];
45     cin >> s[0];
46     dfs(' '+s[0],1);
47     cout << maxx << endl;
48     return 0;
49 }

View Code

（最近要改习惯，用scanf辣）

No matter how you feel, get up , dress up , show up ,and never give up.