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

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;
}

单词接龙