首页 > 代码库 > 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 单词接龙