个人写的迷宫源代码.docx

/ Proj_MiGongGraphDis.cpp : Defines the entry point for the console application./#include stdafx.h #include #include#include #include #include #include #define rightNeib 0#define downNeib 1 #define UpToward 1#define LeftToward 2 #define DownToward 3 #define RightToward 4 #define RowNum 30#define ColumnNum 30#define GridNum 900#define RandWallNum 50000 int aRowNumColumnNum=0;int bGridNum=0;int cGridNum=0;/int bcnt_rowcnt_clolumn=0; /int ccnt_rowcnt_clolumn=0; struct arynode bool upward; bool left; bool downward; bool right; int LastX; int LastY; bool visited; arryRowNumColumnNum; struct Lst int x; int y; struct Lst *next;bool merged;/是否曾经合并int head_x; /当前节点的链表头坐标 int head_y; int head_sign; ;struct Lst * LstArryRowNumColumnNum; int posi_X=0; int posi_Y=0; int Dire_sign=0; int Excecut_sign=0; int N_find=0; int dot_num=1; int m=0; int n=0; int Group_num=0; int start_node_x=0; int start_node_y=0; int end_node_x=RowNum-1; int end_node_y=ColumnNum-1; /-初始化N*N迷宫-start-*/void InitMiGong(); /初始化N*N迷宫void InitArry(arynode arryColumnNum);/初始化迷宫中各个节点的通断情况 void InitSemble();struct Lst *FindTailNode(struct Lst *Pnode);void Merge2semble();int FindPoint(struct Lst *headnod,int X,int Y);int SameSemble(int *point_start_x,int *point_start_y,int *point_end_x,int *point_end_y );int FunJudeEnd();/struct Lst * creatMiG(struct Lst * headnod);/创建迷宫void RemoveRinge(); /初始化-拆墙-绘图void InitArryVisited(arynode arryColumnNum);/初始化-所有的点单元设置为未访问void ResetHeadValue(struct Lst *headnod,int X,int Y); /-初始化N*N迷宫-end-*/ /-行走路径的链表操作-start-*/int funcArry(arynode ArryColumnNum,int i,int j);/查找迷宫出口主函数 struct Lst* headNode; struct Lst* InitLstNode(int InPutX,int InPutY); struct Lst * AddLstNode(struct Lst *head,int InPutX,int InPutY); struct Lst* DelLstNode(struct Lst *head);/删除叶子节点 void printLst(struct Lst *head); /打印行走路径坐标 /-行走路径的链表操作-end-*/ /*绘图函数-start-*/ void DrawDotLst(struct Lst *headnod);/绘制游走点链表 void drawDot(int x,int y); /绘制游走点 void EraseDot(int x,int y);/游走点回退 void drawBlank(int x,int y);/绘制迷宫网格 /*绘图函数-end-*/ int main() InitArry(arry); initgraph(600, 600); / 初始化图形空间 InitMiGong(); /绘制迷宫结点边框 struct Lst * InitRoutHead=InitLstNode(0,0); InitSemble();/每个迷宫格子初始化为一个集合 srand(unsigned)clock();/设定随机数种子 for(unsigned long i=0;i=RandWallNum;i+) / drawDot(0,i/100); / Sleep(10); Merge2semble(); RemoveRinge();/初始化迷宫通断-显示 int SameSemResult=0; SameSemResult=FunJudeEnd(); if(SameSemResult=1)printf(Initial_MiG_OK);/ drawDot(RowNum-1,ColumnNum-1);/for(;) break; RemoveRinge();/初始化迷宫通断-显示headNode=InitLstNode(0,0); InitArryVisited(arry);/funcArry(arry,0,0);for(;) return 0;/*int FunJudeEnd()for(int i=0;iGridNum;i+)for(int j=i+1;jGridNum;j+)int Former_rowN=i/ColumnNum; int Former_colN=i-rowN*ColumnNum;int latter_rowN=j/ColumnNum; int latter_colN=j-rowN*ColumnNum; if(SameSemble(&Former_rowN,&Former_colN,&latter_rowN,&latter_colN)=0) return 0;return 1; */ int FunJudeEnd()int cnt=0;int final_head_x=0;int final_head_y=0;for(int i=0;iRowNum;i+)for(int j=0;jhead_sign=1)final_head_x=i;final_head_y=j; cnt+;if(cnt1) return 0;/* /查找所有链表头for(int ReChk_i=0;ReChk_iRowNum;ReChk_i+)for(int ReChk_j=0;ReChk_jhead_sign=1)if(1) drawDot(ReChk_i,ReChk_j); */ return 1; void InitSemble()/初始化使得每个迷宫格成为一个集合-用链表存储for(int i=0;iRowNum;i+) for(int j=0;jhead_x=i; LstArryij-head_y=j; LstArryij-head_sign=1; LstArryij-merged=false;void Merge2semble()/随机选择2个点。如果2个点不通，则合并2点所在集合int direction=0; int p1_x=0,p1_y=0,p2_x=0,p2_y=0;do p1_x=rand()%RowNum; p1_y=rand()%ColumnNum;while(p1_x=RowNum-1)&(p1_y=ColumnNum-1)|(arryp1_xp1_y.downward=true)&(arryp1_xp1_y.right=true); if(p1_x=RowNum-1) /最下面一行 p2_x=p1_x; p2_y=p1_y+1; direction=rightNeib; if(p1_y=ColumnNum-1)/最右面一列 p2_x=p1_x+1; p2_y=p1_y; direction=downNeib; if(p1_x!=RowNum-1)&(p1_y!=ColumnNum-1) / srand(unsigned)clock(); int Randdire=rand()%2; /其余情况 if(Randdire=rightNeib) p2_x=p1_x; p2_y=p1_y+1; direction=rightNeib; else p2_x=p1_x+1; p2_y=p1_y; direction=downNeib; if( (direction=rightNeib) & (arryp1_xp1_y.right=true) ) return; if( (direction=downNeib) & (arryp1_xp1_y.downward=true) ) return;/ unsigned long p2_x=rand()%RowNum;/ unsigned long p2_y=rand()%ColumnNum; /* int sameClubSign=0; for(int i=0;iRowNum;i+) for(int j=0;jhead_x; int Down_headY=LstArryp2_xp2_y-head_y; int Up_headX=LstArryp1_xp1_y-head_x; int Up_headY=LstArryp1_xp1_y-head_y; / if( LstArryheadXheadY-head_x!=LstArryp1_xp1_y-head_x)/ |(LstArryheadXheadY-head_y!=LstArryp1_xp1_y-head_y) secTailNode-next= LstArryDown_headXDown_headY;ResetHeadValue(LstArryDown_headXDown_headY,Up_headX,Up_headY);LstArryp1_xp1_y-merged=true; / LstArryheadXheadY-head_x=LstArryp1_xp1_y-head_x;/下游方块的链表头-重新设置表头/LstArryheadXheadY-head_y=LstArryp1_xp1_y-head_y; / LstArryheadXheadY-head_sign=0; /LstArryheadXheadY-merged=true; /LstArryp2_xp2_y-merged=true; if(direction=downNeib) arryp2_xp1_y.upward=true; arryp1_xp1_y.downward=true; else if(direction=rightNeib) arryp1_xp2_y.left=true; arryp1_xp1_y.right=true; return; int SameSemble(int *point_start_x,int *point_start_y,int *point_end_x,int *point_end_y )for(int i=0;iRowNum;i+) for(int j=0;jhead_sign=1) if(FindPoint(LstArryij,*point_start_x,*point_start_y)=1) &(FindPoint(LstArryij,*point_end_x,*point_end_y)=1) return 1; return 0;struct Lst *FindTailNode(struct Lst *Pnode)struct Lst * TempNode=Pnode;while(TempNode&(TempNode-next!=NULL) TempNode=TempNode-next;return TempNode;int FindPoint(struct Lst *headnod,int X,int Y) struct Lst *TempNode=headnod;if(headnod=NULL)return 0;while(TempNode&(TempNode-next!=NULL)if(TempNode-x=X&TempNode-y=Y)return 1; TempNode=TempNode-next;if(TempNode-x=X&TempNode-y=Y) return 1;return 0; void ResetHeadValue(struct Lst *headnod,int X,int Y) struct Lst *TempNode=headnod;if(headnod=NULL)return ;while(TempNode&(TempNode-next!=NULL)TempNode-head_x=X;TempNode-head_y=Y;TempNode-merged=true;TempNode-head_sign=0; TempNode=TempNode-next;TempNode-head_x=X;TempNode-head_y=Y;TempNode-merged=true;TempNode-head_sign=0; /*struct Lst * creatMiG(struct Lst * headnod) /创建迷宫 / struct Lst *TempNode=headnod; / AddLstNode(headnod,0,0);int X;int Y;int Cnt=0;/统计的邻居个数/遍历链表中的点，找到所有存在的邻居，并随机选取一个加入链表struct Lst *TempNode=headnod;while(TempNode!=NULL)&(TempNode-next!=NULL)X=TempNode-x; Y=TempNode-y;/判断其邻居 /上方是否有邻居if(X-1=0)&arryX-1Y.visited=false)bCnt=X-1;cCnt=Y;Cnt+; /左方是否有邻居if(Y-1=0)&arryXY-1.visited=false)bCnt=X;cCnt=Y-1;Cnt+; /下方是否有邻居if(X+1RowNum)&arryX+1Y.visited=false)bCnt=X+1;cCnt=Y;Cnt+; /右方是否有邻居if(Y+1next;/链表最后一个结点判断 X=TempNode-x; Y=TempNode-y; /判断其邻居 /上方是否有邻居 if(X-1=0)&arryX-1Y.visited=false) bCnt=X-1; cCnt=Y; Cnt+; /左方是否有邻居 if(Y-1=0)&arryXY-1.visited=false) bCnt=X; cCnt=Y-1; Cnt+; /下方是否有邻居 if(X+1RowNum)&arryX+1Y.visited=false)bCnt=X+1;cCnt=Y;Cnt+;/右方是否有邻居if(Y+1=0)&arrynewNode_X-1newNode_Y.visited=true) arrynewNode_XnewNode_Y.upward=true; arrynewNode_X-1newNode_Y.downward=true; ConnSign=true; /左方是否有邻居 if(ConnSign=false)&(newNode_Y-1=0)&arrynewNode_XnewNode_Y-1.visited=true) arrynewNode_XnewNode_Y.left=true; arrynewNode_XnewNode_Y-1.right=true; ConnSign=true; /下方是否有邻居 if(ConnSign=false)&(newNode_X+1RowNum)&arrynewNode_X+1newNode_Y.visited=true) arrynewNode_XnewNode_Y.downward=true; arrynewNode_X+1newNode_Y.upward=true; ConnSign=true; /右方是否有邻居 if(ConnSign=false)&(newNode_Y+1x=newNode_X; newLstNode-y=newNode_Y; newLstNode-next=NULL; TempNode-next=newLstNode; return headnod; */void InitMiGong()for(int i=0;iRowNum;i+) for(int j=0;jColumnNum;j+) drawBlank(i,j); void RemoveRinge() /拆墙for(int i=0;iRowNum;i+)for(int j=0;jnext!=NULL)drawDot(TempNode-x,TempNode-y);TempNode=TempNode-next; drawDot(TempNode-x,TempNode-y);void drawBlank(int x,int y) /绘制迷宫网格x=x*20;y=y*20; setfillcolor(BLACK); fillrectangle(y,x,y+20,x+20); void drawDot(int x,int y) setfillcolor(GREEN);x=x*20;y=y*20;solidcircle(y+10,x+10,8);void EraseDot(int x,int y)x=x*20;y=y*20; setfillcolor(BLACK);solidcircle(y+10,x+10,8); struct Lst* InitLstNode(int InPutX,int InPutY) struct Lst *headNode= (struct Lst *)malloc(sizeof(struct Lst); if(headNode=NULL) printf(none head point!); return NULL; headNode-x=InPutX; headNode-y=InPutY; headNode-next=NULL; return headNode; struct Lst* AddLstNode(struct Lst *head,int InPutX,int InPutY)/添加节点 struct Lst* tempLst=head; if(tempLst=NULL) printf(none head point!); return NULL; while(tempLst-next!=NULL) tempLst=tempLst-next; struct Lst* newLstNode= (struct Lst *)malloc(sizeof(struct Lst); newLstNode-x=InPutX; newLstNode-y=InPutY; newLstNode-next=NULL; tempLst-next=newLstNode; return head; struct Lst* DelLstNode(struct Lst *head)/删除叶子节点 struct Lst* tempLst=head; if(tempLst=NULL) printf(none head point!); return head; if(tempLst-next=NULL) printf(only head,cant delete!); return head; while(tempLst-next!=NULL&tempLst-next-next!=NULL) tempLst=tempLst-next;struct Lst* lastNode=tempLst-next;free(lastNode);lastNode=NULL;tempLst-next=NULL; return head;void printLst(struct Lst *head) struct Lst* tempLst=head; if(tempLst=NULL) printf(none head point!); while(tempLst-next!=NULL) printf(pointX:%dtpointY:%dn,tempLst-x,tempLst-y); tempLst=tempLst-next; printf(pointX:%dtpointY:%dn,tempLst-x,tempLst-y);/打印最后的节点 int funcArry(arynode ArryColumnNum,int i,int j) Sleep(10); DrawDotLst(headNode); N_find=0; Excecut_sign=0; /向下 if(i+1RowNum)&(Arryij.downward=true)&(Arryi+1j.visited=false)&(Dire_sign!=UpToward)&(Excecut_sign=0) AddLstNode(headNode,i+1,j); Excecut_sign=1; Arryi+1j.LastX=i; Arryi+1j.LastY=j; Arryi+1j.visited=true; Dire_sign=DownToward; printf(Row:%dtColumn:%dn,i+1,j); funcArry(Arry,i+1,j); else N_find+; /向右 if(j+1=0)&(Arryij.upward=true)&(Arryi-1j.visited=false)&(Dire_sign!=DownToward)&(Excecut_sign=0) AddLstNode(headNode,i-1,j); Excecut_sign=1; Arryi-1j.LastX=i; Arryi-1j.LastY=j; Arryi-1j.visited=true; Dire_sign=UpToward; printf(Row:%dtColumn:%dn,i-1,j); funcArry(Arry,i-1,j);