p1019单词接龙,蒟蒻求助!!!
  • 板块题目总版
  • 楼主KMSK
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/9/11 20:35
  • 上次更新2023/11/4 07:02:47
查看原帖
p1019单词接龙,蒟蒻求助!!!
472423
KMSK楼主2021/9/11 20:35

比如说我要搜索a开头的字符串为什么会搜索到a开头的字符串同时会搜索到c开头的字符串呢?,我的代码有搜索结果显示,可以把1019的测试数据输入就一目了然了。(用的深搜加剪枝)

#include<iostream>
using namespace std;
string s[25];
int a[25];
int n;
int ans;
char c;
string merge(string s1,string s2)
{
	if(s1=="")return s2;
	int len1=s1.size();
	int len2=s2.size();
	string s3="",ss="";
	for(int i=0;i<len2;i++)
	{
		s3+=s2[i];
		int k=s1.rfind(s3);
		if((len1-1-k)==i)
		{
			for(int j=0;j<k;j++)
			ss+=s1[j];
			for(int j=0;j<len2;j++)
			ss+=s2[j];
			return ss;
		}
	 }
	 return s1; 
}
void dfs(int k,string s1,string s2)
{
	string ss=s1;
	string ns=merge(s1,s2);
	if(k==2*n||ns==s1)//剪枝:连接之后如果还是之前那个就直接返回 
	{
		int len=ns.size(); 
		cout<<ns<<endl;
		if(ns[0]==c)ans=max(ans,len);
		//cout<<ns<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]<2)
		{
			a[i]++;
			dfs(k+1,ns,s[i]);
			a[i]--;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>s[i];
	cin>>c;
	for(int i=1;i<=n;i++)
	{
		if(s[i][0]==c)
		{
		a[i]++;
		dfs(1,"",s[i]);
		a[i]--;
	}
	  }
	/*for(int i=1;i<=n;i++)
	cout<<s[i][0]<<" ";*/
	cout<<ans<<endl;
    return 0;
	
}
2021/9/11 20:35
加载中...