亿片WA声
查看原帖
亿片WA声
1011696
_lxm楼主2024/7/3 14:59
#include<bits/stdc++.h>
using namespace std;
int n,ans,vis[100];
string words[100],start;
//a是头,b是尾 
int check(string a,string b){
	for(int i=1;i<a.length()&&i<b.length();i++)
		if(a.substr(i,a.length()-1)==b.substr(0,a.length()-i)) return i;
	return 0;
}
void dfs(string s){
	int ls=s.length();
	ans=max(ans,ls);
	for(int i=1;i<n;i++){
		if(vis[i]>=2) continue;
		int ok=check(s,words[i]);
		if(ok){
			vis[i]++;
			dfs(s+words[i].substr(0,ls-ok));
			vis[i]--;
		}
	} 
}
int main(){
	/*单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,
	要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,
	例如 beast 和 astonish,如果接成一条龙则变为 beastonish,另外相邻的两部分不能存在包含关系,例如 at 和 atide 间不能相连。*/
	cin >>n;
	for(int i=1;i<=n;i++) cin >>words[i];
	cin >>start; 
	dfs(start);
	cout <<ans;

	return 0;
}
2024/7/3 14:59
加载中...