呃…變形課上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<iostream> #include<cstring> using namespace std; char a[1010][2];//這個數組的作用就是將每個字符串的開頭和結尾保存下來，方便搜索。。 int vis[1010];//記錄，神奇的vis。 int ant;//記錄有多少個字符串 int dfs(int step) {if(a[step][1]=='m')//搜索到了最后，如果是m那么就符合題意。return 1;for(int i=0;i<ant;i++){if(a[i][0]!=a[step][1]) continue;//如果上一個的結尾和下一個的開頭不一樣。就要跳過循環。if(vis[i]) continue;//如果這個字母已經走過了，也要跳過vis[i]=1;//更新為1if(dfs(i)) return 1;}return 0;//沒有符合條件的，就返回0 } int main() {char b[1010];while(cin>>b){int flag=0;int len=strlen(b);if(b[0]!='0')//0的時候就要結束輸入，開始搜索了。{a[ant][0]=b[0];a[ant][1]=b[len-1];ant++;//!!!}else{for(int i=0;i<ant;i++){if(a[i][0]=='b')找到第一個b，開始往下搜索。{memset(vis,0,sizeof(vis));//將vis數組歸零。。if(dfs(i)){flag=1;cout<<"Yes."<<endl;break;}}}if(!flag) cout<<"No."<<endl;ant=0;//注意將ant歸零。。}}return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的G - 变形课 HDU - 1181（搜索之dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。