下面是题目复述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和 astonish，如果接成一条龙则变为 beastonish ，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。

输入格式

输入的第一行为一个单独的整数 n(n≤20) 表示单词数，以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

输出格式

只需输出以此字母开头的最长的“龙”的长度。

样例说明

连成的“龙”为 atoucheatactactouchoose

Sample Input

touch

cheat

choose

tact

Sample Output

分析过程：

判断题目需要的是最大值，可以考虑使用dfs。
在题目要求中，有两点需要注意：单词可以重复使用但是不能超过两次，前后单词之间不能存在包含关系。
在dfs过程中，需要判断前一个单词和后一个单词是否满足条件，可以先看前一个单词的后面和后一个单词的前面是否构成接龙关系，满足条件就可以把后面单词不重复的部分加入到总数中去。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=500;
char s[N][N];
int num[N];
int n;
int ma=0;
char a;
int len[N];
int tmp=0;
int fi(int a,int b)
{
    int num2=0;
    for(int i=len[a]-1;i>0;i--)//a单词不到头
    {
        if(s[a][i]==s[b][0])//a中字母和b开头字母相同
        {
             for(int j=0;s[a][i+j]!=0;j++)
            {
                if(s[a][i+j]!=s[b][j]&&j!=len[b]-1) return 0;//a不包含b

                num2++;
            }
            return len[b]-num2;
        }
    }
    return 0;//没找到也返回0。
}
void dfs(int x)
{

    for(int i=0;i<n;i++)
    {
        if(num[i]<2&&fi(x,i))
        {
            tmp+=fi(x,i);
            num[i]++;
            dfs(i);
            num[i]--;
            tmp-=fi(x,i);
        }
    }
    if(tmp>ma) ma=tmp;
}
int main()
{
    scanf("%d",&n);
    getchar();
    for(int i=0;i<n;i++)
        scanf("%s",s[i]),len[i]=strlen(s[i]),num[i]=0;
    getchar();
    scanf("%c",&a);

    //先确定首单词再开始搜索
    for(int i=0;i<n;i++)
    {
        tmp=0;//找到新的开头记得把老数据清零
        if(s[i][0]==a)
        {
            tmp+=len[i];
            num[i]++;
            dfs(i);
            num[i]--;
        }
    }
    printf("%d\n",ma);
    return 0;
}

【题解】DFS——单词接龙

下面是题目复述

分析过程：

AC代码：