qq一笔画红包 的c语言解决方法

来由

今天看到一个红包死活一笔画不出来，然后我用c写个段程序用于解决这个问题

思想

主要采用栈来实现路径的记录与回退，灵感来源于迷宫求解问题

程序使用

1. 给顶点标上序号
2. 求出这个图的邻接矩阵
3. 修改程序中宏定义的MAXSIZE为定点数
4. 运行，输入邻接矩阵

代码

#include <stdio.h>
//节点从1开始编号
#define MAXSIZE 20
typedef struct edgeStack
{int from;int to;
}Edge;Edge VisitStack[100]={0};
Edge PathStack[100]={0};
int VTop=-1,PTop=-1，SumEdges=0;void Invisit(int from,int to)
{VTop++;VisitStack[VTop].from=from;VisitStack[VTop].to=to;
}
void Inpath(int from,int to)
{PTop++;PathStack[PTop].from=from;PathStack[PTop].to=to;
}
void Outvisit()
{VTop--;
}
void Outpath()
{PTop--;
}
int Visit(int from,int to) //边未走过则返回1
{int i=0;for(i=0;i<=VTop;i++){if(VisitStack[i].from==from && VisitStack[i].to==to) return 0;if(VisitStack[i].from==to && VisitStack[i].to==from) return 0;}return 1;
}
void find(int edges[][MAXSIZE],int v)
{int i=v,j=0;for(j=1;j<=MAXSIZE;j++){if(Visit(i,j)&&edges[i-1][j-1]==1)     //判断是否走过这条边并且是否有边存在{Invisit(i,j);Inpath(i,j);printf("%d ",i);find(edges,j); //递归访问下一个节点}}if((PTop+1<SumEdges)&&(j>MAXSIZE)) Outpath();
}
int search(int edges[][MAXSIZE])
{int i=0;for(i=1;i<=MAXSIZE;i++){VTop=-1;  //换第一个节点的时候需要清零栈PTop=-1;printf("以%d为第一个点: ",i);find(edges,i);printf("\n");if(PTop+1>=SumEdges) return 1;}return 0;
}
int main()
{int edges[MAXSIZE][MAXSIZE]={0};int i=0,j=0;for(i=1;i<=MAXSIZE;i++){for(j=1;j<=MAXSIZE;j++){scanf("%d",&edges[i-1][j-1]);}}if(search(edges)){printf("\n成功完成一笔画，一种解法为: ");printf("%d ",PathStack[0].from);for(i=0;i<=PTop;i++){printf("%d ",PathStack[i].to);}printf("\n");}else printf("该图无法一次走过所有边，无法一笔画");
}

例子

标序号

求出邻接矩阵

运行输入

得出一笔画顺序