HDU 1181変形レッスンDFS

変形レッスン
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 20254    Accepted Submission(s): 7293
Problem Description
ええと、変形の授業でハリーはちょっと困ったことがありました.彼はHermioneのようにすべての呪文を覚えることができないので、勝手に野球をハリネズミに変えるなんて、変形呪文の統一的な法則を発見しました.もし呪文がaの冒頭のbで終わる単語であれば、その役割はちょうどA物体をB物体にすることです. 
Harryはすでに彼のできるすべての呪文を1つの表に並べて、彼はあなたに彼が先生の宿題を完成できるかどうかを計算してもらいたいと思って、1つのB(ball)を1つのM(Mouse)に変えて、あなたは知っていて、もし彼自身が完成できないならば、彼はHermioneに教えてもらうしかなくて、しかもたくさんのよく勉強する道理を聞かなければなりません.
 
Input
テストデータには複数のグループがあります.各グループには複数の行があり、各行に1つの単語があり、小文字のみを含み、Harryができるすべての呪文である.数字0は入力の終わりを表す.
 
Output
ハリーが彼の宿題を完成できるなら「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
分析:単語の先頭と末尾は接続でき、bで始まり、mで終わる.
#include #include #include #include #include using namespace std; string s[1010],str; bool a[1010],flag; int s_size; void DFS(char c) {     if(flag)    ///枝を切る        return;     for(int i = 0;i < s_size;i++)     {         if(!a[i] && s[i][0] == c)  ///条件を満たす場合は、下へ        {             if(s[i][s[i].size()-1] == 'm')  ///見つけた            {                 flag = 1;                 printf("Yes.");                 return;             }             else             {                 a[i] = 1;                 DFS(s[i][s[i].size()-1]);                 a[i] = 0;             }         }     } } void solve() {     flag = 0;     for(int i = 0;i < s_size;i++)  ///一つ一つ遍歴する.    {         if(s[i][0] == 'b')         {             if(s[i][s[i].size()-1] == 'm')  ///見つけた、出力、終了            {                 flag = 1;                 printf("Yes.");                 break;             }             else    ///見つかりませんでした            {                 a[i] = 1;                 DFS(s[i][s[i].size()-1]);                 a[i] = 0;                 if(flag)    ///見つかったかどうかを判断する                    break;             }         }     }     if(!flag)         printf("No."); } int main() {     s_size = 0;     while(cin >> str)     {         if(str == "0")  ///0に等しい場合は、このテストデータのセットの入力が終了することを示します.        {            ///判断を下す            solve();            ///次のデータ入力の初期化            s_size = 0;             memset(a,0,sizeof(a));         }         else    ///配列に入れる            s[s_size++] = str;     }     return 0; }