题目描述

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

输入描述:

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

输出描述:

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

示例1

输入
5
at
touch
cheat
choose
tact
a
输出
23
说明
连成的“龙”为atoucheatactactouchoose

解答

其实他的思路就是接近裸的深度优先搜索 
最初我的想法是用char类型的字符串但是发现用char类型的字符串并没有string好用然后呢本人就用了string，string各种函数的具体用法大家百度吧或者在我以后的博文中会更新 
好了不罗嗦了具体说一下该怎么写代码 
首先我们定义一个数组use表示当前单词使用的次数w代表单词ans=0,now=1 ans记录龙的长度，now省略头子母 
题目说每个单词最多用两次所以我们要在这里加判断 
大概的思路就是这样，其实实现的话懂了DFS的基本上都能根据思路写出来代码了

先把深度优先搜索的部分码上来
void dfs(int k){
    ans=max(ans,now);
    for(int i=1;i<=n;i++){//依次遍历每个单词 
        if(use[i]<2){
            for(int j=0;j<w[k].length();j++){//判断如果首字母相同那么就比较 
                if(w[i][0]==w[k][j]){
                    int l1=j;
                    int l2=0;
                    while(w[i][l2]==w[k][l1] && l1<w[k].length()){//逐一比较到词尾 
                        l1++;
                        l2++;
                    }
                    if(l1>=w[k].length()){//如果比较完成 
                        now+=w[i].length()-l2;//新的单词减去与上个单词重合的长度 
                        use[i]++; 
                        dfs(i);//以这个单词为新的节点搜索
                        now-=w[i].length()-l2;
                        use[i]--; 
                    }
                }
            }
        }
    }
} 
然后是预处理函数，主要是对use进行处理 
void in(){ 
for(int i=0;i<25;i++){ 
use[i]=0; 
} 
} 
这里用memset(use,0,sizeof(use))也是可以的  
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>
using namespace std;

int n,num;
string w[25];//记录单词 
int use[25];//用来记录单词 
int ans=0,now=1;//ans记录龙的长度，now省略头子母
void dfs(int k){
    ans=max(ans,now);
    for(int i=1;i<=n;i++){//依次遍历每个单词 
        if(use[i]<2){
            for(int j=0;j<w[k].length();j++){//判断如果首字母相同那么就比较 
                if(w[i][0]==w[k][j]){
                    int l1=j;
                    int l2=0;
                    while(w[i][l2]==w[k][l1] && l1<w[k].length()){//逐一比较到词尾 
                        l1++;
                        l2++;
                    }
                    if(l1>=w[k].length()){//如果比较完成 
                        now+=w[i].length()-l2;//新的单词减去与上个单词重合的长度 
                        use[i]++; 
                        dfs(i);//以这个单词为新的节点搜索
                        now-=w[i].length()-l2;
                        use[i]--; 
                    }
                }
            }
        }
    }
} 
void in(){
    for(int i=0;i<25;i++){
        use[i]=0;
    }
}
int main()
{
    in(); 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    cin>>w[0];//把头子母看作一个单词 
    dfs(0);
    printf("%d",ans);
    return 0;
}


来源：Lpy_Now