变形课
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 19133 Accepted Submission(s):
6892
Problem Description
呃......变形课上Harry碰到了一点小麻烦,因为他并不像Hermione那样能够记住所有的咒语而随意的将一个棒球变成刺猬什么的,但是他发现了变形咒语的一个统一规律:如果咒语是以a开头b结尾的一个单词,那么它的作用就恰好是使A物体变成B物体.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且*听一大堆好好学习的道理.
Harry已经将他所会的所有咒语都列成了一个表,他想让你帮忙计算一下他是否能完成老师的作业,将一个B(ball)变成一个M(Mouse),你知道,如果他自己不能完成的话,他就只好向Hermione请教,并且*听一大堆好好学习的道理.
Input
测试数据有多组。每组有多行，每行一个单词,仅包括小写字母,是Harry所会的所有咒语.数字0表示一组输入结束.
Output
如果Harry可以完成他的作业,就输出"Yes.",否则就输出"No."(不要忽略了句号)
Sample Input
so
soon
river
goes
them
got
moon
begin
big
Sample Output
Yes.
Hint
Hint
第二次做这道题，开始超时了。
提前预判要不要进行对该节点扩展，不要调用dfs然后判断改点是不是能扩展。就因为这原因超时的
15ms
/******************************* Date : 2015-12-08 21:36:48
Author : WQJ (1225234825@qq.com)
Link : http://www.cnblogs.com/a1225234/
Name : hdu 1181 ********************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#define LL long long
using namespace std;
int k;
char ch[][];
char a[];
bool flag;
bool vis[];
void dfs(int n)
{
int i,j;
vis[n]=;
if(ch[n][]=='m')
{
flag=;
return;
}
for(i=;i<k;i++)
{
if(ch[i][]==ch[n][])
{
if(vis[i]) continue;
dfs(i);
vis[i]=;
if(flag) return;
}
}
return;
}
int main()
{
freopen("in.txt","r",stdin);
int i,j;
while(scanf("%s",ch[])!=EOF)
{
int len=strlen(ch[]);
ch[][]=ch[][len-];
for(i=;;i++)
{
scanf("%s",a);
if(a[]=='')
break;
int len=strlen(a);
ch[i][]=a[];
ch[i][]=a[len-];
}
k=i+;
flag=;
memset(vis,,sizeof(vis));
for(i=;i<k;i++)
{
if(ch[i][]=='b')
{
dfs(i);
vis[i]=;
}
}
printf("%s\n",flag?"Yes.":"No.");
}
return ;
}