成语接龙(dfs)

成语接龙
Time Limit: 1000 MS Memory Limit: 32768 K
Total Submit: 92(17 users) Total Accepted: 23(14 users) Rating:  Special Judge: No
Description
给出N个成语,通过成语接龙,求接出最长龙的成语个数。

每个成语由至少三个至多8个汉字组成,如果前一个成语的最后一个字和后一个成语的第一个字相同,那么就可以接到一起。

为了将问题简化,每个汉字用4个字母编码代替。保证每个汉字的都有唯一的编码。所有字母均为小写字母,且以第一个成语为开始成语, 每个成语只可以使用一次。

Input
多组测试数据,对每组数据

第一行是一个整数N,代表有N个成语。

接下来N行,每行一个成语。

(N <= 20)

Output
输出最长长度
Sample Input
5

adfkejimejlsgkeh

emiemkwlcuhelmge

gkeheohowehiemie

lmgejoewijfeabcd

emiekejlwejdadfk

Sample Output
4
Source

2014 Winter Holiday Contest 4

注意第一个成语必须是题目给的第一个成语。。。。还有这题真坑啊,如果输入while(cin>>n)一直wa,我也不知道为什么,叉姐说是出题人数据有问题,如果知道为什么的请指点一二。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
struct node
{
    char tou[5];
    char wei[5];
}a[25];
char str[505];
int maxn = 1;
int visit[25];
int n;

int dfs(int deep, int sum)
{
    if(sum > maxn) maxn = sum;

    for(int i = 0; i < n; i++)
    {

        if(!visit[i])
        {
            int ok = 0;
            for(int j = 0; j < 4; j++)
            {
                if(a[deep].wei[j] != a[i].tou[j])
                {
                    ok = 1;

                }
            }

            if(!ok)
            {
                visit[i] = 1;
                dfs(i,sum + 1);
                visit[i] = 0;
            }
        }
    }
}
int main()
{
#ifdef xxz
   freopen("in.txt","r",stdin);
#endif // xxz

    while(scanf("%d",&n) != EOF)
    {

        for(int i = 0; i < n; i++)
        {
            //cin>>str;
            scanf("%s",str);
            int len = strlen(str);
            for(int j = 0; j < 4; j++)
            {
                a[i].tou[j] = str[j];
                a[i].wei[j] = str[len-4+j];
            }
        }
        memset(visit,0,sizeof(visit));
        visit[0] = 1;
         maxn = 1;
        dfs(0,1);
        cout<<maxn<<endl;
      // printf("%d\n",maxn);
    }

    return 0;
}

时间: 11-01

成语接龙(dfs)的相关文章

luogu 1019 单词接龙 dfs细节

P1019 单词接龙 题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连. 输入输出格式 输入格式: 输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,

NOIP2000单词接龙[DFS]

题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连. 输入输出格式 输入格式: 输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单

微信公众平台开发—成语接龙

一.源码 package org.xs.dntown.wx.idiom.modules.web; import java.util.Date; import java.util.List; import java.util.Random; import javax.servlet.http.HttpServletRequest; import org.apache.commons.lang3.StringUtils; import org.springframework.beans.factor

单次接龙dfs洛谷

题目传送门:https://www.luogu.org/problem/show?pid=1019#sub 典型的爆搜,每次更新最大龙长度即可 搜索每个字符串编号,与已经连接好的字符串进行比较,以此往后找,若全部匹配,则可以接龙 注意: 1.自己也可以与自己相连 2.题目中所说的不能存在包含关系是连接好后的相邻两部分 并不是如果是子串就不能连接 否则第一个单词即起始字母无法连接 //Gang #include<iostream> #include<cstring> #include

dfs(洛谷1019 单词接龙NOIp2000提高组第三题)

单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连. 输入格式: 输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每行有一个单词,输入的最后一行为一个单个字符,表示“龙”开头的

单词接龙(codevs 1018)

2000年NOIP全国联赛普及组NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题解 题目描述 Description 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如a

NOIP2000 单词接龙

题三.  单词接龙                (27分)    问题描述    单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连.  输   入  输入的第一行为一个单独的整数n (n<=2

洛谷 P1019 单词接龙 深搜

题目描述 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的"龙"(每个单词都最多在"龙"中出现两次),在两个单词相连时,其重合部分合为一部分,例如 beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at 和 atide 间不能相连. 输入输出格式 输入格式: 输入的第一行为一个单独的整数n (n<=20)表示单词数,以下n 行每

CodeVS 1018-单词接龙

原题 题目描述 Description 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的"龙"(每个单词都最多在"龙"中出现两次),在两个单词相连时,其重合部分合为一部分,例如beast和astonish,如果接成一条龙则变为beastonish,另外相邻的两部分不能存在包含关系,例如at和atide间不能相连. 输入描述 Input Description 输入的第一行为一个单独的整数n(n