成语接龙(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

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;

}