题意：从左下方1开始，一笔画出圣诞老人的屋子(不过话说，圣诞老人的屋子是这样的吗？这算是个屋子么)，输出所有可以的路径。
思路：贴代码。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue> using namespace std;
int head[],tot=,val;//val:用整型值存储结果，因为最后输出是要按大小排序
int vis[];//用来标记边是否已经走过，若已经走过，则接下来就不能走该条边
int len;//满足一笔画的答案个数
int ans[];//存储答案
struct Edge{
int to,next;
}edge[]; //建立双向边
void add(int u,int v){
edge[tot].next=head[u];
edge[tot].to=v;
head[u]=tot++; edge[tot].next=head[v];
edge[tot].to=u;
head[v]=tot++;
} void init(){
memset(head,-,sizeof(head)); //一开始忘记初始化head了。。。
add(,);add(,);add(,);
add(,);add(,);
add(,);add(,);
add(,);
}
//u：当前走到的点；idx表示已经走过了idx条边，总计需要走完8条边
void dfs(int u,int idx){
if(idx==){
val=val*+u;
ans[len++]=val;
val/=;
return;
}
for(int k=head[u];k!=-;k=edge[k].next){
if(vis[k])
continue; //若第k条边已经走过，则继续尝试其它边
int v=edge[k].to;
/*
因为是双向边，相同端点的会有两条，走过其中一条后，另一条也要标记走过，因为每条边只能走一次，一开始就是这里给忽略了。
若k为偶数，第k边端点为u、v，则第k+1边端点也为u、v，要同时标记走过。
若k为奇数，第k边端点为u、v，则第k-1边端点也为u、v，要同时标记走过。
*/
if(k%==){
vis[k]=;
vis[k+]=;
}
else{
vis[k]=;
vis[k-]=;
}
val=val*+u;
dfs(v,idx+);
//最后要恢复原来的值，不能影响之后的遍历
val=val/;
if(k%==){
vis[k]=;
vis[k+]=;
}
else{
vis[k]=;
vis[k-]=;
}
}
} int main()
{
init();
len=;
memset(vis,,sizeof(vis));
val=;
//从左下角1开始dfs
dfs(,); sort(ans,ans+len);
for(int i=;i<len;i++)
printf("%d\n",ans[i]);
return ;
}
贴个书上的参考程序：
#include <iostream>
#include <string>
#include <cstring>
//因为数据量很小，用邻接矩阵，15ms，而且输出顺序即按照大小顺序排。
using namespace std;
int edge[][];
void makeEdge(){
memset(edge,,sizeof(edge));
for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(i!=j)
edge[i][j]=;
}
}
edge[][]=edge[][]=;
edge[][]=edge[][]=;
}
//目前已画了k条边，准备将x扩展为s的第k+1条边的端点
void dfs(int x,int k,string s){
s+=char(x+'');
if(k==){
cout<<s<<endl;
return;
}
for(int y=;y<=;y++){
if(edge[x][y]){
edge[x][y]=edge[y][x]=;
dfs(y,k+,s);
edge[x][y]=edge[y][x]=;
}
}
}
int main()
{
makeEdge();
dfs(,,"");
return ;
}