ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1019　单词接龙

来源：洛谷 ★ 1300

DFS
本题活力0.26按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

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

代码

#include <bits/stdc++.h>
using namespace std;
int ans=0;
vector<string> s(21);
vector<int> vis(21,0);
void dfs(string str,int n)
{ans=max(ans,(int)str.size());
for(int i=0;i<n;i++)
{
    if(vis[i]<2)
    {
        for(int j=1;j<min(str.size(),s[i].size());j++)
        {
            if(str.substr(str.size()-j)==s[i].substr(0,j))
            {
                vis[i]++;
                dfs(str+s[i].substr(j),n);
                vis[i]--;
            }
        }
    }
}
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
    }
    char ch;
    cin>>ch;
    for(int i=0;i<n;i++)
    {if(s[i][0]==ch)
        {
        vis[i]++;
        dfs(s[i],n);
        vis[i]--;
    }}
    cout<<ans;
}