DFS 单词接龙
题目描述
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beastbeastbeast和astonishastonishastonish，如果接成一条龙则变为beastonishbeastonishbeastonish，另外相邻的两部分不能存在包含关系，例如atatat 和 atideatideatide 间不能相连。
输入格式
输入的第一行为一个单独的整数nnn (n≤20n \le 20n≤20)表示单词数，以下nnn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.
输出格式
只需输出以此字母开头的最长的“龙”的长度
输入输出样例
输入
5
at
touch
cheat
choose
tact
a
23
简单dfs,一看不要被吓到，仔细看看还是很简单的。需要注意的是每个单词可以用两次，其余的注意一下细节，这道题还是很容易过的，代码奉上。
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
long long int a,n=-1;
string c;
int x[25]={0};//标记使用的次数
string str[25];
void dfs()
{
//cout<<c<<endl;
int len=c.size();
if(len>n) n=len;
for(int i=0;i<a;i++)
{
if(x[i]<2)
{
for(int j=1;j<=c.size()&&j<str[i].size();j++)
{
if(str[i].substr(0,j)==c.substr(c.size()-j,j)&&x[i]<2)
{
c=c+str[i].substr(j,str[i].size()-j);
x[i]++;
dfs();
c=c.substr(0,c.size()-str[i].size()+j);//回溯 注意
x[i]--;
}
}
}
}
}
int main()
{
cin>>a;
for(int i=0;i<a;i++)
{
cin>>str[i];
}
cin>>c;
dfs();
cout<<n;
} 
查看11道真题和解析
