用户登录
用户注册

分享至

【DFS】有趣的英语角

  • 作者: 进退两男
  • 来源: 51数据库
  • 2021-07-30

问题描述:

某校科技节到了,英语科组张老师要主持一个英语角活动,活动的内容怎样
才有趣呢?张老师为此事伤了很长时间的脑筋。后来,他想到了一个单词接龙比
赛活动,内容是这样的:是一个与我们经常玩的成语接龙相类似的游戏,现在我
们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”
(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为
一部分,例如 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来做,相同就递归下去


CodeCode:

#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;
}
软件
前端设计
程序设计
Java相关