用栈+循环实现走迷宫及演示c++

 1 #include  2 #include "mystack.h"
 3 #include  4 #include string.h>
 5 #include  6 using namespace std;
 7 #define MAXROW 10
 8 #define MAXLINE 10
 9 //1 代表墙，2 走过的路，0 代表路 Stack s; Point prePts[MAXROW][MAXLINE];
10 int maze[MAXROW][MAXLINE] =
11 { 
12 1,1,1,1,1,1,1,1,1,1,
13 0,0,0,1,1,1,1,1,1,1,
14 1,1,0,1,1,1,1,1,1,1,
15 1,1,0,0,0,0,1,1,1,1,
16 1,1,0,1,1,0,1,1,1,1,
17 1,1,0,1,1,0,1,1,1,1,
18 1,1,1,1,1,0,1,1,1,1,
19 1,1,1,1,1,0,0,0,1,1,
20 1,1,1,1,1,1,1,0,0,0,
21 1,1,1,1,1,1,1,1,1,1,
22 };
23 Stack s;
24 Point sp = {1,0},ep= {8,9},prePts[MAXROW][MAXLINE];
25 void displyMaze()
26 {
27     for(int i=0;i)
28     {
29         for(int j=0; j)
30         {
31             if(maze[i][j] == 1)
32                 printf("%2s"," *");
33             else if(maze[i][j] == 2)
34                 printf("%2s"," #");
35             else printf("%2s"," ");
36         }
37         putchar(10);
38     }
39     printf(" ====================\n");
40 }
41 void visit(int x,int y,Point prep)
42 {
43     Point p={x,y}; //当前点
44     push(&s,p);
45     prePts[x][y] = prep;
46 }
47 int main()
48 {
49     displyMaze();
50     initStack(&s);
51     memset(prePts,0xff,sizeof(Point)*MAXROW*MAXLINE);
52     push(&s,sp);
53     Point t;
54     int flag = 0;
55     while(!isStackEmpty(&s))
56     {
57         t = pop(&s);
58         maze[t._x][t._y] = 2; //不走回头路
59         //左
60         if(t._y-1>=0&&maze[t._x][t._y-1] == 0)
61             visit(t._x,t._y-1,t);
62         //右
63         if(t._y+19&&maze[t._x][t._y+1] == 0)
64             visit(t._x,t._y+1,t);
65         //上
66         if(t._x-1>=0&&maze[t._x-1][t._y] == 0)
67             visit(t._x-1,t._y,t);
68         //下
69         if(t._x+19&&maze[t._x+1][t._y] == 0)
70             visit(t._x+1,t._y,t);
71         system("cls");
72         displyMaze();
73         Sleep(1);
74         if(t._x == ep._x && t._y == ep._y)
75         {
76             flag = 1;
77             clearStack(&s);
78         }
79     }
80     if(flag == 1)
81     {
82         printf("find right path\n");
83         Point t = ep;
84         while(t._y != -1)
85         {
86             printf("(%2d,%2d)\n", t._x, t._y);
87             t = prePts[t._x][t._y];
88         }
89     }
90     else
91         printf("there is no way\n");
92     return 0;
93 }

 1 #include "mystack.h"
 2 #include  3 #include  4 void initStack(Stack * ps)
 5 {
 6     ps->top = NULL;
 7 }
 8 int isStackEmpty(Stack * ps)
 9 {
10     return ps->top == NULL;
11 }
12 void push(Stack *ps, Point ch)
13 {
14     SNode * cur = (SNode *)malloc(sizeof(SNode));
15     cur->_data = ch;    
16     cur->_next = ps->top;
17     ps->top = cur;
18 }
19 Point pop(Stack *ps)
20 {
21     SNode * t = ps->top;
22     Point ch = t->_data;
23     ps->top = ps->top->_next;
24     free(t);
25     return ch;
26 }
27 void clearStack(Stack * ps)
28 {
29     SNode * t;
30     while(ps->top)
31     {
32         t = ps->top;
33         ps->top = ps->top->_next;
34         free(t);
35     }
36 }

 1 #ifndef __MYSTACK_H__
 2 #define __MYSTACK_H__
 3 typedef struct _Point
 4 {
 5     int _x;
 6     int _y;
 7 } Point;
 8 typedef struct _SNode
 9 {
10     Point _data;
11     struct _SNode * _next;
12 }SNode;
13 typedef struct _Stack
14 {
15     SNode * top;
16 }Stack;
17 void initStack(Stack * ps);
18 int isStackEmpty(Stack * ps);
19 void push(Stack *ps, Point ch);
20 Point pop(Stack *ps);
21 void clearStack(Stack * ps);
22 #endif