多种迷宫求解问题.docx

1. #include 2. #include 3. #include 4. using namespace std;5.6. #definemap_width 117. #definemap_high 11 8.9. class MyList10. 11. protected :12. MyList *p_next,*p_head, *p_tail , *p_current ,*p_forward;13. int i_passed_m;14. int i_passed_n;15. int map_showmap_widthmap_high;16.17. public:18. MyList();19. MyList();20. MyList* CreateList();21. virtual void Inset(int m ,int n);22. void Delete();23. void Show();24. int get_m();25. int get_n();26. ;27.28. code/mylist.cpp29.30.31. #include mylist.h32.33.34. MyList:MyList()35. 36. MyList *p_next = NULL ,*p_head = NULL , *p_tail = NULL , *p_current =NULL , *p_forward =NULL;37. 38. MyList:MyList()39. MyList * MyList:CreateList()40. 41. MyList *p_current = new MyList;42. p_current-p_next = NULL;43. p_tail = p_head = p_current;44. return p_head;45. 46.47. void MyList:Inset(int m ,int n)48. 49. MyList *p_current = new MyList;50.51. p_current-i_passed_m = m; /给数据52. p_current-i_passed_n = n; 53.54. p_tail-p_next = p_current;55. p_current-p_forward = p_tail;56. p_tail = p_current;57. p_tail-p_next = NULL;58. 59.60. void MyList:Delete()61. 62. p_tail = p_tail-p_forward;63. p_tail-p_next = NULL;64. 65.66. void MyList:Show()67. 68. 69. int i_show_mapmap_widthmap_high =0;70. i_show_mapmap_high-2map_width-2 = 1;71. 72. while( p_head-p_next != NULL)73. 74. p_head = p_head-p_next; /后移75. /couti_passed_m i_passed_ni_passed_mp_head-i_passed_n = 1;77. 78. /endl of while 79. for (int m = 0 ; m map_high ; m+) /输出路径80. 81. coutendl;82. for (int n = 0 ; n map_width ; n+)83. 84. /coutroad_statemn;85. if ( 1 =i_show_mapmn )86. 87. cout;88. 89. else90. 91. couti_passed_m;101. 102.103. int MyList:get_n()104. 105. return p_tail-i_passed_n;106. 复制代码1. /main 2. /2009.10.7 varius 5h3. #include mylist.h4. #define chukou 3 5. #define map_wall 06. #definemap_road 17. #definemap_passed 28.9. int* make_map();10.11. int main()12. 13.14. int i_x =1 ,i_y = 1 ;15. srand( (unsigned)time( NULL ) ); 16. int road_statemap_widthmap_high = 0;17.18. for(int j = 1 ; j map_high-1 ; j+) /随机生成路或者墙19. 20. for (int k = 1 ; kmap_width-1 ; k+)21. 22. /Sleep(1);23. road_statejk = rand()%2;24. if ( 0 = road_statejk )25. 26. road_statejk = rand()%2;27. 28. /ijk=random（100）%2;29. 30. 31. road_state11 = 1;/入口32. road_statemap_width-2map_high-1 = 1; 33. road_statemap_width-2map_high-2 = 3;/出口34.35.36. /输出图形37. for (int m = 0 ; m map_high ; m+)38. 39. coutendl;40. for (int n = 0 ; n map_width ; n+)41. 42. /coutroad_statemn;43. if ( 0 =road_statemn )44. 45. cout;46. 47. else48. 49. cout;50. 51. 52. 53. Sleep(1000);54. /getchar();55.56. MyList shit;57. shit.CreateList();58. shit.Inset(1,1);59. /找路的代码60. while( TRUE )61. 62. if ( 3 = road_statei_x+1i_y) /出口判断63. 64. coutn出来了n;65. getchar();66. break;67. 68. if ( 3 = road_statei_xi_y+1) /出口判断69. 70. coutn到出口n;71. getchar();72. break;73. 74. if ( road_statei_x+1i_y=1 ) /朝下75. 76. /coutendl当前位置状态road_statei_x+1i_yendl;77. /couti_xi_y;78. i_x+;79. road_statei_xi_y = 0;80. shit.Inset(i_x,i_y);81. /cout下;82. / Sleep(400);83. cout;84.85. 86. else if ( 1 = road_statei_xi_y+1 ) /朝右87. 88. i_y+;89. road_statei_xi_y = 0;90. shit.Inset(i_x,i_y);91. /cout右;92. /Sleep(400);93. cout ;94. 95. else if ( 1 = road_statei_x-1i_y ) /朝上96. 97. i_x-;98. road_statei_xi_y = 0;99. shit.Inset(i_x,i_y);100. /cout上;101. /Sleep(400);102. cout ;103. 104. else if ( 1 = road_statei_xi_y-1 ) /朝左105. 106. i_y-;107. road_statei_xi_y = 0;108. shit.Inset(i_x,i_y);109. /cout左;110. /Sleep(400);111. cout ;112. 113. else if (TRUE) /死路情况114. 115. if ( 1 = i_x)116. 117. coutn没出口 endl;118. getchar();119. exit(0);120. 121. shit.Delete();122. /*if ( 1= i_x & 1 = i_y)/没路情况123. 124. cout没有出口;125. getchar();126. exit(0);127. */128.129. i_x =shit.get_m();130. i_y =shit.get_n();131. / cout死路 往回走一格 ;132.133. 134. /end of while 135.136. shit.Show();137.138. getchar();139.140. return 0;141. 迷宫图案，白色代表通道，黑色代表墙。迷宫入口坐标(1,1),出口坐标(8,8) 01234567890123456789# include using namespace std;const int SIZE_X=10;const int SIZE_Y=10;/data structstruct mPoint int x; int y; bool can_move_to; mPoint(int rx=0,int ry=0,bool rcan_move_to=false) x=rx; y=ry; can_move_to=rcan_move_to; next=NULL; mPoint *next;/function declarationclass mStackpublic: mStack();/constructor int push(mPoint point); mPoint pop(); int getLength(); mPoint getTop(); void printStack();private: mPoint *base;/base pointer mPoint *top; /top pointer int length; /length of stack;int main() mPoint mpArraySIZE_XSIZE_Y; bool initArraySIZE_XSIZE_Y=false,false,false,false,false,false,false,false,false,false, false,true ,true ,false,true ,true ,true ,false,true ,false, false,true ,true ,false,true ,true ,true ,false,true ,false, false,true ,true ,true ,true ,false,false,true ,true ,false, false,true ,false,false,false,true ,true ,true ,true ,false, false,true ,true ,true ,false,true ,true ,true ,true ,false, false,true ,false,true ,true ,true ,false,true ,true ,false, false,true ,false,false,false,true ,false,false,true ,false, false,false,true ,true ,true ,true ,true ,true ,true ,false, false,false,false,false,false,false,false,false,false,false;/迷宫矩阵 for(int i=0;iSIZE_X;i+)/init for(int j=0;jSIZE_Y;j+) mpArrayij.x=i; mpArrayij.y=j; mpArrayij.can_move_to=initArrayij; mPoint startp(1,1,true);/entry mPoint endp(8,8,true); /exit mStack mpath; mpath.push(startp); mPoint mp=startp; while(true) if(mp.x=endp.x & mp.y=endp.y) break;/success if(mpArraymp.x+1mp.y.can_move_to)/search down mpArraymp.x+1mp.y.can_move_to=false; mpath.push(mPoint(mp.x+1,mp.y); mp=mpArraymp.x+1mp.y; continue; if(mpArraymp.x-1mp.y.can_move_to)/search up mpArraymp.x-1mp.y.can_move_to=false; mpath.push(mPoint(mp.x-1,mp.y); mp=mpArraymp.x-1mp.y; continue; if(mpArraymp.xmp.y+1.can_move_to)/search right mpArraymp.xmp.y+1.can_move_to=false; mpath.push(mPoint(mp.x,mp.y+1); mp=mpArraymp.xmp.y+1; continue; if(mpArraymp.xmp.y-1.can_move_to)/serch left mpArraymp.xmp.y-1.can_move_to=false; mpath.push(mPoint(mp.x,mp.y-1); mp=mpArraymp.xmp.y-1; continue; if(0=mpath.getLength() coutNo path!endl; return -1; mpath.pop(); mp=mpath.getTop(); coutPath:next=mpNode; top=mpNode; return +length;mPoint mStack:getTop() return *top;mPoint mStack:pop() if(lengthnext!=NULL) if(top-next-next=NULL) delete(top-next); top-next=NULL; break; top=top-next; if(length=1) delete(base); base=top=NULL; length-; return retPoint;int mStack:getLength() return length;void mStack:printStack() mPoint *p=base; while(p!=NULL) cout(x,y)next; 本程序堆栈用单向动态链表实现，当然可以用其他数据结构，比如双向链表。程序输出结果：Path:(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)(8,8)#include #include #define MAX_X 18#define MAX_Y 38int mainground (int x,int y);void endshow ();main()int x=1,y=0,key,outline=0;system(color 0a);mainground(x,y);while(key!=q) key=getch(); switch(key) case w: mainground(-x,y); if(outline=mainground(x,y)=1) x+; break; case s: mainground(+x,y); if(outline=mainground(x,y)=1) x-; break; case a: mainground(x,-y); if(outline=mainground(x,y)=1) y+; break; case d: mainground(x,+y); if(outline=mainground(x,y)=1) y-; break; default:mainground(x,y);break; printf(兄弟您走好!恕不远送.n); getch();int mainground (int x,int y) int i=0,j=0; int mapMAX_XMAX_Y= 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1, 1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,0,1,0,1,1, 1,0,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,1,0,1,1, 1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,1, 1,1,1,1,0,1,0,1,1,0,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,0,0,0,1,0,1,0,1,1, 1,0,0,0,0,1,0,1,1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,0,1,0,0,0,1,0,0,1, 1,1,1,0,1,1,0,1,1,0,1,1,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1, 1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,1, 1,0,1,1,1,1,0,1,1,0,1,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1, 1,0,1,1,0,0,0,0,1,0,1,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1, 1,0,0,0,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1, 1,1,1,0,1,1,1,0,1,0,0,1,0,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,1, 1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,0,1,0,1,1,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1, 1,0,1,1,1,1,1,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1, 1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1; if(mapxy=0) system(cls); printf(简单的走迷宫小游戏升级版C语言实现VC+环境调试通过 By walkandthinkn); printf(Blog:/walkandthinkn); printf(上:w 下:s 左:a 右:d 退出:qn); mapxy=2; for(i=0;iMAX_X;i+) for(j=0;jMAX_Y;j+) if(mapij=1) printf( x02,mapij); else if(mapij=2) printf( x0C,mapij); else printf( ,mapij); printf(n); if(x=16&y=37) system(cls); endshow(); else return 0; else return 1;void endshow() printf(=n); printf(= 恭喜您顺利过关! =n); printf(= By U#0h4x0r =n); printf(= Blog:/walkandthink =n); printf(=n); system(start iexplore /walkandthink); while(1) Sleep(50); system(color 01); Sleep(50); system(color 02); Sleep(50); system(color 03); Sleep(50); system(color 04); Sleep(50); system(color 05); Sleep(50); system(color 06); Sleep(50); system(color 07); Sleep(50); system(color 0a); Sleep(50); system(color 0b); Sleep(50); system(color 0c); Sleep(50); system(color 0d); Sleep(50); system(color 0e); Sleep(50); system(color 0f); #include #include using namespace std;void SelectSort(int * iArray,int iSize);/record the Positiontypedef struct _tagPointint x;int y;Point;/reloaded the != operatorbool operator !=(const Point & pt0,const Point & pt1)return !(pt0.x = pt1.x) & pt0.y = pt1.y);/define the Directionenum enumDirectdirUp = 8,dirDown = 2,dirLeft = 4,dirRight = 6;/Show your Positionvoid ShowPosition(const Point & ptPos)cout your position is row: ptPos.x + 1 col: ptPos.y + 1 endl;/check the Road can movebool CanMove(Point ptTmp,char * cMap,int iRow,int iCol)return *(cMap + ptTmp.x * iCol + ptTmp.y) = 0;/display the Mapvoid ShowMap(Point ptTmp,char * cMap,int iRow,int iCol)for(int i = 0;i iRow;i+)for(int j = 0;j iCol;j+)if(i = ptTmp.x) & (j = ptTmp.y)cout -;elsecout *(cMap + i * iCol + j) ;cout endl;void main(void)char cMap910 = 1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,1,0,1,1,1,1,0,1,0,0,0,0,1,0,1,1,0,1,0,0,1,0,0,0,1,1,0,1,1,1,1,0,1,1,1;Point ptStart = 8,1;Point ptEnd = 8,6;Point ptPos = -1,-1;int iDirect = dirDown;bool bStart = true;while(ptPos != ptEnd & ptPos != ptStart)/clear the screensystem(cls);/show the mapShowMap(ptPos,(char *)cMap,9,10);/give the tipcout Are you Move to? endl;cout 8- UP, 2- Down, 4- Left, 6-