1172: 单词接龙（XCOJ 暴力DFS）

1172: 单词接龙

时间限制: 1 Sec 内存限制: 128 MB
提交: 12 解决: 5

题目描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

输入

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出

只需输出以此字母开头的最长的“龙”的长度

样例输入

touch

cheat

choose

tact

样例输出

提示

样例中，连成的“龙”为atoucheatactactouchoose

暴力往下搜索

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 char ch[25][20];
 7 int vis[25];
 8 int n,Max;
 9 int judge(int x,int y)
10 {
11     int i,j;
12     //cout<<ch[x]<<" "<<ch[y]<<endl;
13     int len1=strlen(ch[x]);
14     int len2=strlen(ch[y]);
15     for(i=len1-1;i>=0&&(len1-i)<=len2;i--)
16     {
17         int k1=i,k2=0;
18         for(;k1<len1;k1++,k2++)
19             if(ch[x][k1]!=ch[y][k2])
20                 break;
21         if(k1==len1)
22         {
23             if((len1-i)==strlen(ch[y]))
24                 return 0;
25             else
26                 return len1-i;
27         }
28     }
29     return 0;
30 }
31 void dfs(int f,int sum)
32 {
33     int i,j;
34     if(sum>Max)
35         Max=sum;
36     for(i=1;i<=n;i++)
37     {
38         if(vis[i]>=2)
39             continue;
40         int ans=judge(f,i);
41         if(ans!=0)
42         {
43             vis[i]++;
44             //cout<<strlen(ch[i])-ans<<endl;
45             dfs(i,sum+strlen(ch[i])-ans);
46             vis[i]--;
47         }
48     }
49     return;
50 }
51 int main()
52 {
53     int i,j;
54     freopen("in.txt","r",stdin);
55     while(scanf("%d",&n)!=EOF)
56     {
57         Max=0;
58         memset(vis,0,sizeof(vis));
59         for(i=1;i<=n;i++)
60             scanf("%s",ch[i]);
61         scanf("%s",ch[0]);
62         dfs(0,strlen(ch[0]));
63         printf("%d
",Max);
64     }
65     return 0;
66 }