1019 单词接龙

难度：普及/提高-

题目类型：深搜

提交次数：5

涉及知识：深搜

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

代码：

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 int n;
 5 char a[20][20];
 6 int len;
 7 int maxx=0;
 8 int visited[20];
 9 bool finished(){
10     for(int i = 1; i<=n; i++)
11         if(!visited[i]) {
12             return false;
13         }
14     return true;
15 }
16 int split(string a, string b){
17     int i;
18     int minn;
19     minn = 20;
20     if(a.length()<b.length())
21         if(a==b.substr(0, a.length())) return 0;//排除被包含情况 
22     if(a.length()>b.length())
23         if(a.substr(a.length()-b.length(),b.length())==b) return 0;
24     for(i = 1; i < a.length(); i++){
25         if(a.substr(i, a.length()-i) == b.substr(0, a.length()-i)){
26             if(a.length()-i<b.length())
27                 if(a.length()-i<minn)
28                     minn = a.length()-i;
29         }
30     }
31     if(minn == 20) return 0;
32     else return minn;
33 }
34 void dfs(int cur){
35     //if(finished()){
36       //  if(len>maxx) maxx = len;
37        //return;
38     //}
39     maxx = max(len,maxx);
40         for(int i = 1; i <= n; i++){
41             string s1 = a[cur];
42             string s2 = a[i];
43             if(visited[i]!=2&&split(s1, s2)){
44                 visited[i]++;
45                 len += s2.length()-split(s1,s2);
46                 dfs(i);
47                 len -= s2.length()-split(s1,s2);
48                 visited[i]--;
49             }
50                 
51         } 
52     
53 }
54 int main(){
55     cin>>n;
56     int i;
57     for(i = 1; i <= n; i++)
58         cin>>a[i];
59     char start;
60     cin>>start;
61     string ss;
62     for(i = 1; i <= n; i++)
63         if(a[i][0]==start){
64             ss = a[i];
65             len=ss.length();
66             visited[i] = 1;
67             dfs(i);
68             visited[i] = 0;
69         }
70     //if(n==1&&split(ss,ss)) maxx = 2*ss.length()-split(ss, ss);
71     cout<<maxx;
72     return 0;
73 }

备注：

作为一道真题实在太坑了。耗了一下午，AC了还是心情郁结。除了我自己脑残没审好题，和犯的其他错误以外，出题意图真是让人百思不得其解，不就是想考个dfs吗？

解题思路比较顺畅，结构也挺清晰的，遇到的所有问题都是细节问题。

最开始我dfs里的边界条件是一个finished函数，因为我以为每个单词都得用上。正是因为这样，加上一个单词最多可以用2次（此处是个大坑），只有一个单词时，就没法往下dfs了，也就是说envelop最长时应该是两个自己连起来，但照我那么写第一个单词就不会尝试自己连自己。后来我就把只有一个单词的情况单拎出来判断。

题目表达不清的地方：两个相邻单词不可以有包含关系，但两个一模一样的单词却可以连在一起（就是只有真子集不能连在一起），而且两个单词相接，重叠部分是可以自己任意取得？！那么就得取得越短越好了。

然后就是最让我崩溃的一个坑，不过这大概主要赖我自己审题不清。不是每一个单词都能用到！！这我tm悟了一个多小时。不过出题人的表述也脱不了干系，他说“假设龙一定存在”，正常人不应该理解成所有词都可以串接起来吗？可事实上，可以连不起来，那最大长度就是以规定字母开头最长的那个单词的长度。这样的话finished函数也卵用没有了。直接在len更新的时候更新max就行了。我注释掉的部分完全没有用了，包括把n==1的情况单拎出来也没有意义了。

这个dfs看起来怪怪的，因为它似乎没有了边界条件，接不下去的时候就停了。

总之，这一下午虽然效率低了些，应该来说还是颇有收获的。dfs掌握得大概差不多了。

可我还是鄙视这道题。