一本通1220单词接龙//洛谷 P1019 单词接龙 官方题解

· · 题解

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

【输入】 输入的第一行为一个单独的整数n(n≤20)表示单词数，以下n行每行有一个单词（只含有大写或小写字母，长度不超过20），输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。

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

【输入样例】 5 at touch cheat choose tact a 【输出样例】 23

标程如下：

#include<bits/stdc++.h>

using namespace std;

int n;

string str[30];

int len_str,sum=0;

int times[30]={0};

void dfs(int x)
{

    int i,j;
    int p,q;
    int num;
    int work;
    for(i=1;i<str[x].length();i++)
    {
        num=0;
        for(j=1;j<=n;j++)
        {
            if(times[j]<2)
            {
                if(str[x][i]==str[j][0])
                {
                    p=i,q=0,work=0;
                    while(p<=str[x].length()-1)
                    {
                        if(str[x][p]!=str[j][q])
                        {
                            num++;
                            work++;
                            break;
                        }
                        p++;
                        q++;
                    }
                    if(!work&&q!=str[j].length())
                    {
                        len_str+=str[j].length()-q;
                        times[j]++;
                        dfs(j);
                        len_str-=str[j].length()-q;
                        times[j]--;
                    }
                }
                else num++;
              }
              else num++;
        }
        if(num==n&&i==str[x].length()-1)
        {
              if(sum<len_str) sum=len_str;
              return;
        }
    }
}
int main()
{

    int i;
    cin>>n;
    for(i=1;i<=n+1;i++)      cin>>str[i];
    for(i=1;i<=n;i++)
        if(str[i][0]==str[n+1][0])  
        {
            times[i]++;
            len_str=str[i].length();
            dfs(i);
        }
    cout<<sum<<endl;
    return 0;
}