hdu 1181 變形課 DFS

變形課

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)

Total Submission(s): 18231    Accepted Submission(s): 6556

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.


   
    
     Hint
    Hint
   
    
Harry 可以念這個咒語:"big-got-them".
        

Source Gardon-DYGG Contest 1  

Recommend JGShining   |   We have carefully selected several similar problems for you:   1016  1175  1010  1180  1258  //隻能說做題一定要認真小心，否則隻能大意失荊州，這道題隻要用結構體來存每個字元竄的首字母和末尾的字母，利用深搜的方法，在搜尋完了，要取消标志，但是如果是首字母為‘b‘，的話，就不需要取消，因為這會搜尋完了，絕對不可能是它了，參考代碼如下：  

#include<stdio.h>
#include<string.h>
int w,k;
int v[100010];
struct s
{
	char x,y;
}a[100010];
void dfs(int u)
{
	int i,j;
	//v[u]=1;
	if(a[u].y=='m')
	{
		w=1;
		return;
	}
	else
	{
		for(i=0;i<k;i++)
		{
			if(!v[i]&&a[i].x==a[u].y)
			{
				v[i]=1;
				dfs(i);
				v[i]=0;
			}
		}
	}
}
int main()
{
	char s[10010];
	while(scanf("%s",s)!=EOF)
	{
		int len,i;
		w=k=0;
		if(s[0]=='0')
		{
			printf("No\n");
			continue;
		}
		len=strlen(s);
		a[k].x=s[0];
		a[k].y=s[len-1];
		k++;
		while(scanf("%s",s)!=EOF)
		{
			if(s[0]=='0')
				break;
			len=strlen(s);
			a[k].x=s[0];
			a[k].y=s[len-1];
			k++;
		}
		//memset(v,0,sizeof(v));
		for(i=0;i<k;i++)
		{
			if(a[i].x=='b')
			{
				memset(v,0,sizeof(v));
				v[i]=1;
				dfs(i);
			}
			if(w)
				break;
		}
		if(w)
			printf("Yes.\n");
		else
			printf("No.\n");
	}
}