B20 DFS 单词接龙

#include<iostream>
using namespace std;

const int N=25;
int n,ans;
int used[N]; //每个单词的使用次数
string word[N];

void dfs(string s){ //对当前串s接龙
  int ls=s.size();
  ans=max(ans,ls);
  for(int i=0; i<n; i++){ //枚举每个单词
    string w=word[i];
    int lw=w.size();
    for(int j=1; j<ls&&j<lw; j++){ //枚举位置
      if(used[i]<2&&s.substr(ls-j)==w.substr(0,j)){
        used[i]++; //使用次数+1
        dfs(s+w.substr(j)); //dfs新串
        used[i]--;
        break;     //已是最长接法，结束j
      }
    }
  }
}
int main(){
  cin>>n;
  for(int i=0; i<n; i++) cin>>word[i];
  string start; cin>>start;
  start="*"+start; //在前面添加一个字符，不用特判了
  dfs(start);
  cout<<ans-1<<endl;
}

scy:

#include<bits/stdc++.h>
using namespace std;
char str[25][110];
int use[25],ans,n;
int canlink(char s1[], char s2[],int k)//学会字符串传参数，判断s1的后k个字母和s2的前k个字母是否相同 
{
    for(int i=0;i<k;i++) if(s1[strlen(s1)-k+i]!=s2[i]) return 0;
    return 1;
}
void solve(char s[],int len)
{
    ans=max(ans,len);
    for(int i=1;i<=n;i++)if(use[i]<2)
    {
        for(int j=1;j<min( strlen(s), strlen(str[i]) );j++)//枚举头尾衔接的长度 
			if( canlink(s,str[i],j) )
	        {
	        	use[i]++;
	            solve(str[i],len+strlen(str[i])-j);
	            use[i]--;
	        }
    }
}
main()
{
    scanf("%d",&n);
    memset(use,0,sizeof(use));
    for(int i=1;i<=n;i++) scanf("%s",str[i]);
    scanf("%s",str[0]+1);
    str[0][0]=' '; 
    ans=0;solve(str[0],strlen(str[0]+1));
    printf("%d\n",ans);
    return 0; 
}

B20 DFS 单词接龙

#include<iostream>
using namespace std;

const int N=25;
int n,ans;
int used[N]; //每个单词的使用次数
string word[N];

void dfs(string s){ //对当前串s接龙
  int ls=s.size();
  ans=max(ans,ls);
  for(int i=0; i<n; i++){ //枚举每个单词
    string w=word[i];
    int lw=w.size();
    for(int j=1; j<ls&&j<lw; j++){ //枚举位置
      if(used[i]<2&&s.substr(ls-j)==w.substr(0,j)){
        used[i]++; //使用次数+1
        dfs(s+w.substr(j)); //dfs新串
        used[i]--;
        break;     //已是最长接法，结束j
      }
    }
  }
}
int main(){
  cin>>n;
  for(int i=0; i<n; i++) cin>>word[i];
  string start; cin>>start;
  start="*"+start; //在前面添加一个字符，不用特判了
  dfs(start);
  cout<<ans-1<<endl;
}

#include<bits/stdc++.h>
using namespace std;
char str[25][110];
int use[25],ans,n;
int canlink(char s1[], char s2[],int k)//学会字符串传参数，判断s1的后k个字母和s2的前k个字母是否相同 
{
    for(int i=0;i<k;i++) if(s1[strlen(s1)-k+i]!=s2[i]) return 0;
    return 1;
}
void solve(char s[],int len)
{
    ans=max(ans,len);
    for(int i=1;i<=n;i++)if(use[i]<2)
    {
        for(int j=1;j<min( strlen(s) , strlen(str[i]) );j++)//枚举头尾衔接的长度 
			if( canlink(s,str[i],j) )
	        {
	        	use[i]++;
	            solve(str[i],len+strlen(str[i])-j);
	            use[i]--;
	        }
    }
}
main()
{
    scanf("%d",&n);
    memset(use,0,sizeof(use));
    for(int i=1;i<=n;i++) scanf("%s",str[i]);
    scanf("%s",str[0]+1);
    str[0][0]=' '; 
    ans=0;solve(str[0],strlen(str[0]+1));
    printf("%d\n",ans);
    return 0; 
}