HDOJ2188 哈密顿绕行世界问题（DFS）

标准的DFS，用STL里的stack可简便地完成。

[cpp]
/*HDOJ2188
作者：陈佳润
2013-04-12
*/
#include
#include
using namespace std;

int Case;
stack 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< for(i=1;i<=21;i++){
cout< if(i!=21)
cout<<" ";
}
cout< 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;
}