单词接龙--C++

题目描述

输入格式

输出格式

输入

输出

一、AC代码

二、代码分析

三、vector加深理解

题目描述

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

输入格式

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

输出格式

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

输入

5
at
touch
cheat
choose
tact
a

输出

一、AC代码

#include<bits/stdc++.h>
#define N 26
using namespace std;

vector<int> ver[N],edge[N];//二维数组 匹配的单词编号和匹配长度
string word[N];
int n,res=0;
int st[N];

void dfs(string u, int k)
{
	st[k] ++;
	res = max(res, (int)u.size());
	
	for(int i = 0; i < ver[k].size(); i++)
	{
		int point = ver[k][i], d = edge[k][i];
		if(st[point]<2)
			dfs(u+word[point].substr(d), point);
	}
	st[k]--;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>word[i];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			string a=word[i], b=word[j];
			int len=min(a.size(),b.size());
			for(int k=1;k<len;k++)
			{
				if(a.substr(a.size()-k)==b.substr(0,k))
				{
					ver[i].push_back(j);
					edge[i].push_back(k);
					break;
				}
			}
		}
	
	string head;
	cin>>head;
	for(int i=1;i<=n;i++)
		if(head[0]==word[i][0]) dfs(word[i],i);
	cout<<res<<endl;
	return 0;
}