【DFS】有趣的英语角

问题描述：

某校科技节到了，英语科组张老师要主持一个英语角活动，活动的内容怎样
才有趣呢？张老师为此事伤了很长时间的脑筋。后来，他想到了一个单词接龙比
赛活动，内容是这样的：是一个与我们经常玩的成语接龙相类似的游戏，现在我
们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”
（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为
一部分，例如 beast 和 astonish，如果接成一条龙则变为 beastonish，另外相
邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。对于给定的 N
个单词和一个开头的字母，谁最先完成这个最长的单词接龙谁就获胜，现在请你
帮忙编写一个程序实现这个单词接龙游戏功能。
数据输入：
从文件 english.in 中读入数据，输入的第一行为一个单独的整数 n (n<=20)
表示单词数，以下 n 行每行有一个单词，输入的最后一行为一个单个字符，表
示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
数据输出：
结果输出到文件 english.out 中，只需输出以此字母开头的最长的“龙”的
长度。

---

输入输出样例：

english.in
5
at
touch
cheat
choose
tact
a

english.out
23
（连成的“龙”为 atoucheatactactouchoose）

---

思路：

这题我们可以用dfs来做，相同就递归下去

---

$Code$:

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int n,jl[30],maxx;
char ch[30][30]; 
int check (int l,int r,int d)//下面dfs判断相同用
{
	for (int i = 0; i < strlen (ch[l]) - r; ++i)
	  if (ch[d][i] != ch[l][r + i] || i >= strlen (ch[d]) - 1)return 0;
	  return 1;
}
void dfs (int l,int r,int len)//dfs，len是长度
{
	maxx = max (maxx, len);
	for (int i = 1; i <= n ; ++i)
	{
		if (jl[i] < 2 && check (l,r,i))
		{
			jl[i]++;
			for (int j = 1; j < strlen (ch[i]); ++j)
	        dfs(i,j,len + strlen(ch[i]) - strlen(ch[l]) + r);
            jl[i]--;
		}
	}
}
int main ()
{
	freopen ("english.in","r",stdin);
	freopen ("english.out","w",stdout);
	maxx = -111212213;
	scanf ("%d", &n);
	for (int i = 1; i <= n ; ++i)  cin>>ch[i];
    cin>>ch[0][0];
    dfs(0, 0, 1);
    printf("%d",maxx);
	return 0;
}

本文地址：https://blog.csdn.net/hunkwu/article/details/108182796