HDOJ 1181 变形课

BFS就好了

变形课

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 9011 Accepted Submission(s): 3360

Problem Description

呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且被迫听一大堆好好学习的道理.

Input

测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.

Output

如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)

Sample Input

sosoonrivergoesthemgotmoonbeginbig0

Sample Output

Yes.

Hint

Hint

Harry 可以念这个咒语:"big-got-them".

Source

Gardon-DYGG Contest 1

Recommend

JGShining

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 struct w
 9 {
10     char s;
11     char e;
12 }ww[100000];
13 
14 int vis[100000];
15 
16 queue<w> q,e;
17 
18 int main()
19 {
20 
21     string str;
22     int cur=0;
23     memset(vis,0,sizeof(vis));
24     while(cin>>str)
25     {
26         if(str[0]=='0')
27         {
28             int OK=0;
29             while(!q.empty())
30             {
31                struct w k;
32                k=q.front();
33                if(k.e=='m')
34                {
35                    OK=1;
36                    break;
37                }
38                else
39                for(int i=0;i<cur;i++)
40                {
41                    if(vis[i]==0&&ww[i].s==k.e)
42                    {
43                        q.push(ww[i]);
44                        vis[i]=1;
45                    }
46                }
47                q.pop();
48             }
49 
50             if(OK) cout<<"Yes."<<endl;
51             else cout<<"No."<<endl;
52 
53             q=e;
54             memset(vis,0,sizeof(vis));
55             cur=0;
56 
57         }
58         else
59         {
60           int len=str.length();
61           ww[cur].s=str[0];
62           ww[cur].e=str[len-1];
63 
64           if(ww[cur].s=='b')
65           {
66             q.push(ww[cur]);
67             vis[cur]=1;
68           }
69            cur++;
70         }
71     }
72 
73 
74     return 0;
75 }