首页 > 代码库 > 1019 单词接龙

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掌握得大概差不多了。

可我还是鄙视这道题。

1019 单词接龙