HDOJ2188 哈密頓繞行世界問題（DFS）

標准的DFS，用STL裡的stack可簡便地完成。

[cpp]
/*HDOJ2188
作者：陳佳潤
2013-04-12
*/ 
#include<iostream>  
#include<stack>  
using namespace std; 
 
int Case; 
stack<int> S; 
int map[22][5];//記錄數據  
int used[22];//標記是否走過  
int start;//記錄起點  
 
void DFS(){ 
    int top,i; 
    if(S.size()>21)//如果經過的地點超過21個，則退出  
        return; 
    if(S.top()==start && (S.size()<21&&S.size()!=1))//如果遇到起點，但不是終點，則退出  
        return; 
    if(S.size()==21 && S.top()==start){//如果遇到終點  
        int temp[22]; 
        for(i=21;i>0;i--){ 
            temp[i]=S.top(); 
            S.pop(); 
        } 
        //輸出  
        cout<<Case<<":  "; 
        for(i=1;i<=21;i++){ 
            cout<<temp[i]; 
            if(i!=21) 
                cout<<" "; 
        } 
        cout<<endl; 
        for(i=1;i<=21;i++){ 
            S.push(temp[i]); 
        } 
        Case++; 
        return; 
    } 
    top=S.top(); 
    for(i=1;i<=3;i++){ 
        if(!used[map[top][i]]){ 
            used[map[top][i]]=1;//標志已經有了  
            S.push(map[top][i]);//入棧  
            DFS();//遞歸  
            used[map[top][i]]=0;//去除標志  
            S.pop();//出棧  
        } 
    } 
} 
 
int main(){ 
    int i; 
    //freopen("1.txt","r",stdin);  
    while(cin>>map[1][1] && map[1][1]){ 
        cin>>map[1][2]>>map[1][3]; 
        for(i=2;i<=20;i++) 
            cin>>map[i][1]>>map[i][2]>>map[i][3]; 
        cin>>start; 
        for(i=1;i<=20;i++)//初始化  
            used[i]=0; 
        S.push(start); 
        Case=1; 
        DFS(); 
    } 
    return 0; 
}