10.06 [codevs] 单词接龙题记
题目：
题目描述 Description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入描述 Input Description
输入的第一行为一个单独的整数n(n<=20)表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出描述 Output Description
只需输出以此字母开头的最长的“龙”的长度
样例输入 Sample Input
5
at
touch
cheat
choose
tact
a
样例输出 Sample Output
23
0.简记
算是第一个自己完成的有一点难度的题目qwq，中途犯了很多奇怪且脑残的错误，
原先的习惯一直是把它们记纸上，既然入了贵系坑，习惯也要渐渐改过来嘛qwq。
再加上代码记纸上实在是懒得写，字也不好看。。。
1.错误
0.审题
忘记是求最长串；
忘记了两次的限制；
1.return -1的位置放错
逻辑混乱
2.知识点
dfs
回溯
字符串处理
3.进步
熟练使用注释调试法
4.代码
#include <string>
#include <iostream>
using namespace std;
int used[20];
string word[20];
string beg;
int maxlen=0;
int tlen=1;
int n;
int check(string a,string b)
{
int len1=a.size(),len2=b.size();
for (int i=1;i<=len1;i++)
{
if (a.substr(len1-i,i)==b.substr(0,i))
{
return len2-i;
}
}
return -1;
}
void dfs (string s)
{
for (int i=0;i<n;i++)
{
if (used[i]!=2)
{
if (check(s,word[i])>0)
{
tlen += check(s, word[i]);
used[i]++;
maxlen=max (maxlen,tlen);
dfs (word[i]);
used[i]--;
tlen -= check(s, word[i]);
}
}
}
}
int main() {
for (int i=0;i<n;i++)
{
used[i]=0;
}
cin >>n;
for (int i=0;i<n;i++)
{
cin >>word[i];
}
cin >>beg;
dfs (beg);
cout << maxlen;
return 0;
}
