nyoj 99-单词拼接 (euler, dfs) 99-单词拼接
内存限制:64MB
时间限制:3000ms
特判: No
通过数:7
提交数:14
难度:5
题目描述:
给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
输入描述:
第一行是一个整数N(0<N<20)，表示测试数据的组数 每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。
输出描述:
如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".") 如果不存在拼接方案，则输出 ***
样例输入:
2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm
样例输出:
aloha.arachnid.dog.gopher.rat.tiger ***
C/C++：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #include <stack> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <climits> 11 #include <bitset> 12 #define eps 1e-6 13 using namespace std; 14 15 int in[30], out[30], my_book[1010], my_route[1010], n; 16 17 struct node 18 { 19 int h, t; 20 char s[35]; 21 }my_str[1010]; 22 23 bool cmp(node a, node b) 24 { 25 return strcmp(a.s, b.s) < 0; 26 } 27 28 int euler() 29 { 30 int my_begin = -1, my_end = -1; 31 for (int i = 0; i < 26; ++ i) 32 { 33 if (out[i] != in[i]) 34 { 35 if (out[i] - in[i] == 1 && my_begin == -1) my_begin = i; 36 else if (out[i] - in[i] == -1 && my_end == -1) my_end = i; 37 else return -1; 38 } 39 } 40 if (my_begin > -1 && my_end > -1) return my_begin; 41 if (my_begin == -1 && my_end == -1) 42 { 43 for (int i = 0; i < 26; ++ i) 44 if (out[i] != 0) return i; 45 } 46 return -1; 47 } 48 49 bool dfs(int my_loc_int, int cnt) 50 { 51 if (cnt == n) return true; 52 for (int i = 0; i < n; ++ i) 53 { 54 if (my_book[i] || my_str[i].h < my_loc_int) continue; 55 else if (my_str[i].h > my_loc_int) return false; 56 else 57 { 58 my_book[i] = 1; 59 my_route[cnt] = i; 60 if (dfs(my_str[i].t, cnt + 1)) return true; 61 my_book[i] = 0; 62 } 63 } 64 return false; 65 } 66 67 int main() 68 { 69 ios::sync_with_stdio(false); 70 int t; 71 scanf("%d", &t); 72 while (t --) 73 { 74 /** 75 初始化 76 */ 77 memset (in, 0, sizeof(in)); 78 memset (out, 0, sizeof(out)); 79 memset (my_book, 0, sizeof(my_book)); 80 81 /** 82 输入数据 83 */ 84 scanf("%d", &n); 85 for (int i = 0; i < n; ++ i) 86 { 87 scanf("%s", my_str[i].s); 88 int len = strlen(my_str[i].s); 89 my_str[i].h = my_str[i].s[0] - 'a'; 90 my_str[i].t = my_str[i].s[len - 1] - 'a'; 91 out[my_str[i].h] ++; 92 in[my_str[i].t] ++; 93 } 94 95 /** 96 @parm: my_begin 开始位置的首字母对应ASC - 'a' 97 */ 98 int my_begin = euler(); 99 if (my_begin == -1) 100 { 101 printf("*** "); 102 continue; 103 } 104 sort(my_str, my_str + n, cmp); 105 /** 106 判断是否能找出这样一条路径来 107 */ 108 if (dfs(my_begin, 0)) 109 { 110 for (int i = 0; i < n-1; ++ i) 111 printf("%s.", my_str[my_route[i]].s); 112 printf("%s ", my_str[my_route[n - 1]].s); 113 } 114 else 115 { 116 printf("*** "); 117 } 118 } 119 120 return 0; 121 }