题解 | #单词接龙#

using namespace std;
int n,ans=0;
string a[25];
string dragon;
int g[25][25],use[25];//use数组记录使用单词数
void dfs(string th,int k)
{
	ans=max(ans,(int)th.size());//ans记录连接后龙的长度
    /*if(ans>(int)dragon.size())//如果ans大于龙的长度，那么龙就等于传进来th，即新长龙
		dragon=th;*/
	for(int i=0;i<n;i++)//循环寻找下一个可连接单词
	{
		if(g[k][i]&&use[i]<2)//g数组不为0，表明可连接
		{
			use[i]++;
			dfs(th+a[i].substr(g[k][i]),i);//接龙，进行不重复连接；
			use[i]--;
		}
	}
}
int main()
{
	cin>>n;
	char per;
	for(int i=0;i<n;i++)	cin>>a[i];
	cin>>per;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			for(int k=1;k<min(a[i].size(),a[j].size());k++)//处理包含关系
			if(a[i].substr(a[i].size()-k)==a[j].substr(0,k))//判断重复首尾
			{
				g[i][j]=k;//记录重复首尾字符数
				break;//记录就退出，保证记录最小重复数
			}
		} 
	}
	for(int i=0;i<n;i++)
	{
		if(per==a[i][0])//查找第一个单词，可能以per为首字符的单词有多个
		{
			use[i]++;//记录使用次数
			//dragon=a[i][0];//初始龙
			dfs(a[i],i);//进行深搜，寻找下一个可连接单词
			use[i]--; //回溯
		} 
	}
	cout<<ans<<endl;
	//cout<<dragon;输出最长龙
}