HDOJ 1181 變形課 DFS

AC 781MS 476K，思路非常簡單的一個搜索題，深搜很簡單，題目意思有點不明確，即單詞必須首尾相連

此外還必須注意，若單詞裡面有多個b開頭的單詞，必須依次搜索，當然如果已經找到了符合的答案就可以break了，放在一個隊列裡，模擬dfs就可以了

AC代碼：

[cpp] 
#include <iostream>  
#include <string>  
#include <cstdio>  
#include <cmath>  
#include <vector>  
#include <algorithm>  
#include <sstream>  
#include <cstdlib>  
#include <fstream>  
#include <queue>  
using namespace std; 
bool visit[100010];  //訪問標記  
vector<string> buf; //存放所有單詞  
queue<string> start;//用來存放b開頭的單詞  
int flag; 
void dfs(string s){ 
    if(s[s.size()-1]=='m'){ 
        flag=1; 
        return ; 
    } 
    for(int i=0;i!=buf.size();i++) 
    { 
        if(visit[i])continue; 
        if(flag)return ;       //只要求一組滿足的答案即可  
         
        string tmp1=buf[i]; 
        if(s[s.size()-1]==tmp1[0]){ 
            visit[i]=1; 
            dfs(tmp1); 
            visit[i]=0; 
        } 
    } 
} 
int main() 
{ 
 
    string tmp,s; 
    while(cin>>tmp){ 
        if(tmp[0]=='b')start.push(tmp); 
        buf.push_back(tmp); 
        while(cin>>tmp&&tmp!="0"){ 
        if(tmp[0]=='b')start.push(tmp); 
        buf.push_back(tmp);} 
        int len=buf.size(); 
        memset(visit,0,sizeof(visit)); 
        flag=0; 
        while(!start.empty()){  //多次搜索  
            s=start.front(); 
            start.pop(); 
            for(int i=0;i!=buf.size();i++){ 
                if(s==buf[i]){ 
                    visit[i]=1; 
                    break; 
                } 
            } 
            dfs(s); 
            if(flag){ 
                break; 
            } 
        } 
        if(flag)cout<<"Yes."<<endl; 
        else cout<<"No."<<endl; 
        buf.clear(); 
         
    } 
    return 0; 
 
}