算法：DFS+考你阅题
题目描述：
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
此题深坑，误人子弟，如果就普通的搜索只得66分
注意（看了题解后发现的= =）：
- 所谓“两部分不能存在包含关系”，是指两部分接龙后不能长度不增加。例如ababab和ababab，可以接成ababababab，但不能为ababab。
- 接龙时，如果两个单词接龙后的单词有多种情况，要尽可能保证接龙后的单词最长。例如cabab和ababc，一定要接成cabababc，为而不是cababc。（也就是说在枚举确定两个单词是否可以相接时可以从后往前枚举）
做好这两个，就能A了
上代码：
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string word[21];
int vis[21]; //2次为访问过2次
int n;
int ans = 0;
void dfs(string str, int o) //o是指是添加哪一个单词的下标
{
if(vis[o] > 2) return; //如果添加的已经超过了2，则不判断
//cout << str << endl;
if(str.size() > ans) ans = str.size(); //更新最大值
int i, j, k, pos;
for(i = 1; i <= n; i++)
{
if(vis[i] < 2) //如果没有用到2次
{
//如果有包含关系 并且要取最后面的！注意！
//如果两个单词接龙后的单词有多种情况，要尽可能保证接龙后的单词最长。例如cabab和ababc，
//一定要接成cabababc，为而不是cababc。（也就是说在枚举确定两个单词是否可以相接时可以从后往前枚举）
pos = -1;
for(j = 1; j < str.size(); j++)
{
if(str[j] == word[i][0])
{
for(k = 1; k < word[i].size() && k+j < str.size(); k++)
if(str[j+k] != word[i][k]) break;
if(k+j == str.size() && k != word[i].size()) //有重合
pos = j; //pos记录最后面那个能匹配的下标
}
}
if(pos != -1) //有重合并且下标到最后一个
{
string t = str;
t.append(word[i], k, word[i].size()-k+1); //添加除了重合部分的word进入新串
if(t == str) continue;
vis[i]++; //设置标志
dfs(t, i);
vis[i]--; //清除标志，因为后面可能还会用到i
}
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> word[i];
char begin;
cin >> begin;
for(int i = 1; i<= n; i++)
if(word[i][0] == begin)
{
vis[i]++; //初始赋值
dfs(word[i], i);
memset(vis, 0, sizeof(vis)); //要注意清除
}
cout << ans;
return 0;
}