218
HDU 1181 變形課
變形課Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 11220 Accepted Submission(s): 4156
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.
注：Harry 可以念這個咒語:"big-got-them".
#include<stdio.h>
#include<string.h>
struct node
{
int value;
int flag;
};
int prove;
node a[26][26];
void DFS(node a[][26], int frist)
{
int i;
if(prove==1)
return ;
if(frist==12)
{
printf("Yes.\n");
prove = 1;
return ;
}
for(i=0;i<26;i++)
if(i==frist)
continue;
else
{
if(a[frist][i].value==1&&a[frist][i].flag==0)
{
a[frist][i].flag = 1;
DFS(a,i);
a[frist][i].flag = 0;
}
}
return ;
}
int main()
{
char str[100];
int n,st,en;
memset(a,0,sizeof(a));
prove = 0;
while(gets(str))
{
if(str[0] == '\0')
break;
if(str[0] == '0')
{
DFS(a, 1);
if(prove == 0)
printf("No.\n");
memset(a, 0, sizeof(a));
prove = 0;
}
else
{
n = strlen(str);
st = str[0] - 'a';
en = str[n -1] - 'a';
a[st][en].value = 1;
}
}
return 0;
}
最後更新：2017-04-03 12:55:00