Problem Description
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
Sample Input
so
soon
river
goes
them
got
moon
begin
big
0
Sample Output
Yes.
1 #include <stdio.h>
2 #include <string.h>
3 struct node
4 {
5 char head, tail;
6 }c[10000];//用来记录字符串的首字母和最后一个字母
7 char str[10000];//记录输入的字符串
8 int used[10000], flag, cnt;//used用来记录该字符串是否已被查找过，flag记录查找结果，cnt记录字符串的个数
9 void dfs(int x)//利用深搜解决问题，x是首字母为b的字符串的数组下标
10 {
11 if(c[x].tail == 'm')//当找到最后一个字符为m的字符串时，就可以返回了
12 {
13 flag = 1;//用flag记录搜索后的结果，如果找到末字符为m的字符串，令flag=1
14 return ;
15 }
16 for(int i = 0; i < cnt; i++)//查找首字符与上一个字符串的末字符相同的字符串，直到找到末字符为m的字符串为止
17 {
18 if(c[i].head == c[x].tail && !used[i])//找到首字符与上一个字符串的末字符相同且未经查找的字符串，标记，进行下一次查找
19 {
20 used[i] = 1;
21 dfs(i);
22 }
23 }
24 }
25 int main()
26 {
27 int len;
28 getchar();
29 while(~scanf("%s",str))//先输入一个字符串
30 {
31 cnt = 0, flag = 0;
32 if(str[0] != '0')//如果输入的字符串不为0的话，记录它的首字符和末字符
33 {
34 len = strlen(str);
35 c[cnt].head = str[0];
36 c[cnt].tail = str[len - 1];
37 cnt++;
38 }
39 getchar();
40 while(~scanf("%s",str))//继续输入字符串，直到输入0为止，并记录每一个字符串的首字符和末字符
41 {
42 getchar();//要吸收掉换行符
43 if(str[0] == '0')
44 break;
45 else
46 {
47 len = strlen(str);
48 c[cnt].head = str[0];
49 c[cnt].tail = str[len - 1];
50 cnt++;
51 }
52 }
53 for(int j = 0; j < cnt; j++)//查找首字符为b的字符串，找到后，标记，利用深搜查找末字符为m的字符串
54 {
55 if(c[j].head == 'b')
56 {
57 used[j] = 1;
58 dfs(j);
59 }
60 }
61 if(flag) printf("Yes.
");//如果找到末字符为m的字符串，输出Yes.，否则输出No.
62 else printf("No.
");
63 }
64 return 0;
65 }