《数据结构与算法分析》课程设计——迷宫问题

中国矿业大学信控学院

 

一、 问题描述

 

问题中迷宫可用方阵[m,n]表示，0表示能通过，1表示不能通过。若要从从左上角[1,1]进入迷宫，设计算法，寻求一条从右下角 [m,n] 出去的路径。我们用递增的数来代表寻找出口方向与步数，用-2来代表寻找过程中找错的路径。

 

二、 需求分析

 

需要先创建一个迷宫，在开始后就开始搜寻，当一个点周围有0点（改点并不是以搜寻过的点），那么到这里继续往下搜，如果搜到尽头那么就要倒回去，在搜寻倒回去的周围还有为搜寻过得0点，因此需要一个存储算法，要满足后入先出，那么就是栈，利用栈就可以满足需求。

 

三、 算法分析

 

1.    首先先定义栈，本问题中，不需要在中间插入与弹出，插入与弹出操作均在栈头，因此我们利用顺序栈。

并且该栈与实验课的栈不同，因为要满足实际需求，所以我们需要定义步数以及改点所在的位置以及临近路径的位置在我们栈中，具体操作如下。

 1 //记录通道块在迷宫矩阵当中的横、纵坐标 
 2 struct position {
 3     int x;
 4     int y;
 5 };
 6 
 7 //放入栈当中的通道块元素 
 8 struct selement {
 9     int ord;//记录步数
10     position p;//记录位置 
11     int di;//记录下一次测试这一路径的临近路径的位置 
12 };
13 
14 struct mystack {
15     selement* base;
16     selement* top;
17     int stacksize;
18 };

2.    栈的一些列基础操作，例如创建栈，判断栈是否为空，取栈顶元素，获取栈长，入栈，出栈。上述操作类似学校实验中基本操作，这里不在叙述，详见附录中全部代码。

 

3.    接下来创建迷宫，这里迷宫利用数组来生成，x轴为n，y轴为m

   n为18，m为15。生成方法简单，这里不在叙述，详见附录中全部代码。

 

4.    接下来定义如何走这个迷宫，考虑我们用0作为通道，1作为墙壁，那么搜寻一个点的上下左右0就是可以通过，1就是不能通过。利用以下循环来完成目标：

步骤1：挪到0处的点并且把刚才位置入栈，让改点改为步数，让步数加一，然后继续搜索其上下左右（除去刚才通过的点）如果有0，继续执行步骤1。

步骤2：如果周围的点无0（除去刚才已经通过的点），让改点改为-2，那么就出栈，把路径调到刚才的那个点，并且把步数减一，然后执行步骤1，搜寻其上下左右（出去刚才走错的点以及入这个点之前的点）。

直至入栈点是终点那么退出循环。

代码如下：

 1 do
 2     {
 3         if (pass(curp))
 4         {
 5             footprint(curp, curstep);//可走就在迷宫里面留下足迹 
 6 //创建一个栈元素，存储可行路径的相关值
 7             selement e;
 8             e.di = 1;// 下一个路块为这一个路块的右边的路块 
 9             e.ord = curstep;
10             e.p.x = curp.x;
11             e.p.y = curp.y;
12             push(&path, e);//将路径块入栈 
13 if (curp.x == m - 2 && curp.y == n - 2) break; //如果被压入的路径块到了迷宫的终点就退出循环
14             //找到下一个被试块
15 curp = nextposition(curp, 1);//找到前一个被试块东面的路径块作为被试块
16             curstep++;//被探索的步数加一 
17         }
18         else//如果当前被试路径不能够通过的话 
19         {
20             if (!isstackempty(&path))
21             {
22                 selement e;
23                 pop(&path, &e);
24                 curstep--;
25                 //将这一段所有的周围路径都已经被测试过的路径从栈中清除 
26                 while (e.di == 4 && !isstackempty(&path)) {
27                     markprint(e.p);
28                     pop(&path, &e);
29                     curstep--;
30                 }
31                 //如果当前栈顶还有未被测试的路径就测试剩余的周围路径 
32                 if (e.di<4)
33                 {
34                     curp = nextposition(e.p, e.di + 1);
35                     e.di++;
36                     curstep++;
37                     push(&path, e);
38                 }
39             }
40         }
41     } while (!isstackempty(&path));

5.    在定义上述代码中如何去搜寻，按照从右到下再到左再到上的方法搜寻。代码如下：

 1 //按顺时针方向从右开始寻找矩阵当中某一个位置的临近位置 
 2 position nextposition(position now, int direction)
 3 {
 4     position next;
 5     int x = now.x;
 6     int y = now.y;
 7     switch (direction)
 8     {
 9         //右 
10         case 1: {
11         next.x = x;
12         next.y = y + 1;
13         break;
14         }
15             //下 
16         case 2: {
17         next.x = x + 1;
18         next.y = y;
19         break;
20         }
21             //左
22         case 3: {
23         next.x = x;
24         next.y = y - 1;
25         break;
26         }
27             //上
28         case 4:{
29         next.x = x - 1;
30         next.y = y;
31         break;
32         }
33         default:break;
34     }
35     return next;
36}

6.    定义是否可以通过函数，是就返回ture不是就返回false。代码如下：

 1 //辅助函数考察当前路径能否通过 
 2 bool pass(position posi)
 3 {
 4     //只有路径所在位置的数字为0的是可以走的 
 5     if (maze[posi.x][posi.y] == 0)
 6     {
 7         return true;
 8     }
 9     return false;
10 }

7.    定义是入栈和出栈时如何修改迷宫数组中的值。代码如下：

 1 //改变改点为步骤数 
 2 void footprint(position p, int step)
 3 {
 4     maze[p.x][p.y] = step;
 5 }
 6 
 7 //路径不可走的话就留下-2的标记 
 8 void markprint(position p)
 9 {
10     maze[p.x][p.y] = -2;
11}

8.    定义打印迷宫函数，这个就是遍历整个数组，过程简单这里不在叙述，见附录中全部代码。

四、 结论

 

 编辑ing...

 

五、 参考文献

[1] 严蔚敏，吴伟民——《数据结构》清华大学出版社2004.2.1

 

六、 附录

 

完整代码如下：

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #define stack_init_size 100
  4 #define stackincrement 10
  5 
  6 //记录通道块在迷宫矩阵当中的横、纵坐标 
  7 struct position {
  8     int x;
  9     int y;
 10 };
 11 
 12 //放入栈当中的通道块元素 
 13 struct selement {
 14     int ord;//记录步数
 15     position p;//记录位置 
 16     int di;//记录下一次测试这一路径的临近路径的位置 
 17 };
 18 
 19 struct mystack {
 20     selement* base;
 21     selement* top;
 22     int stacksize;
 23 };
 24 
 25 //创建一个栈如果创建成功则返回1，否则就返回0
 26 int initstack(mystack* s)
 27 {
 28     s->base = (selement*)malloc(stack_init_size * sizeof(selement));//为栈分配初始空间 
 29     if (!s->base) return 0;
 30     s->top = s->base;//设定为空栈 
 31     s->stacksize = stack_init_size;
 32     return 1;
 33 }
 34 
 35 //判断栈是否为空，如果是空的就返回0，否则就返回1 
 36 int isstackempty(mystack* s)
 37 {
 38     if (s->top == s->base) return true;
 39     return false;
 40 }
 41 
 42 //获取栈顶元素,如果栈为空就返回0 否则就返回1
 43 int gettop(mystack* s, selement* e)
 44 {
 45     if (isstackempty(s)) return 0;
 46     e = s->top - 1;
 47     return 1;
 48 }
 49 
 50 //获取栈的长度，并且通过程序返回 
 51 int stacklength(mystack* s)
 52 {
 53     return s->top - s->base;
 54 }
 55 
 56 //插入元素e为新的栈顶元素，插入成功则返回1，否则返回0 
 57 int  push(mystack* s, selement e)
 58 {
 59     if (s->top - s->base >= stack_init_size)
 60     {
 61         s->base = (selement*)realloc(s->base, (s->stacksize + stackincrement) * sizeof(selement));
 62         if (!s->base) return 0;
 63         s->top = s->base + s->stacksize;
 64         s->stacksize += stackincrement;
 65     }
 66     *(s->top) = e;
 67     s->top++;
 68     return 1;
 69 }
 70 
 71 //弹出栈顶元素赋值给e弹出成功返回1，弹出失败返回0
 72 int pop(mystack* s, selement* e)
 73 {
 74     if (isstackempty(s)) return 0;
 75     *e = *(s->top - 1);
 76     s->top--;
 77     return 1;
 78 }
 79 
 80 //定义墙元素为1 可走路径为0 已知路径为curstep 不能够通过的路径为-2 
 81 #define m 15
 82 #define n 18
 83 int maze[m][n] = {  { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 },
 84                     { 1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1 },
 85                     { 1,0,1,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1 },
 86                     { 1,0,1,1,1,0,1,0,1,1,0,1,0,1,1,0,0,1 },
 87                     { 1,0,0,0,0,0,1,0,1,1,0,1,0,0,0,0,1,1 },
 88                     { 1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1 },
 89                     { 1,1,1,0,0,1,1,0,1,1,0,0,0,1,1,1,1,1 },
 90                     { 1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1 },
 91                     { 1,1,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1 },
 92                     { 1,0,0,1,1,1,1,1,1,0,1,1,0,1,0,0,1,1 },
 93                     { 1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,1,1,1 },
 94                     { 1,0,0,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1 },
 95                     { 1,1,0,1,0,1,0,1,1,1,0,0,0,1,1,1,1,1 },
 96                     { 1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,1 },
 97                     { 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 } };
 98 
 99 //辅助函数考察当前路径能否通过 
100 bool pass(position posi)
101 {
102     //只有路径所在位置的数字为0的是可以走的 
103     if (maze[posi.x][posi.y] == 0)
104     {
105         return true;
106     }
107     return false;
108 }
109 
110 //按顺时针方向从右开始寻找矩阵当中某一个位置的临近位置 
111 position nextposition(position now, int direction)
112 {
113     position next;
114     int x = now.x;
115     int y = now.y;
116     switch (direction)
117     {
118         //右 
119     case 1: {
120         next.x = x;
121         next.y = y + 1;
122         break;
123     }
124             //下 
125     case 2: {
126         next.x = x + 1;
127         next.y = y;
128         break;
129     }
130             //左
131     case 3: {
132         next.x = x;
133         next.y = y - 1;
134         break;
135     }
136             //上
137     case 4:
138     {
139         next.x = x - 1;
140         next.y = y;
141         break;
142     }
143     default:break;
144     }
145     return next;
146 }
147 
148 //改变改点为步骤数 
149 void footprint(position p, int step)
150 {
151     maze[p.x][p.y] = step;
152 }
153 
154 //路径不可走的话就留下-2的标记 
155 void markprint(position p)
156 {
157     maze[p.x][p.y] = -2;
158 }
159 
160 //打印出迷宫矩阵 
161 void display_migong()
162 {
163     for (int i = 0; i<m; i++)
164     {
165         for (int j = 0; j<n; j++)
166         {
167             if (maze[i][j]<0)
168                 printf("%d ", maze[i][j]);
169             else if (maze[i][j]<10)
170                 printf("%d  ", maze[i][j]);
171             else
172                 printf("%d ", maze[i][j]);
173         }
174         printf("\n");
175     }
176 }
177 
178 int main()
179 {
180     
181     //迷宫程序主体
182     mystack  path;//记录路径的栈
183     initstack(&path);//初始化路径数组
184     position curp;//当前被试位置
185     display_migong();
186     //初始化当前位置为矩阵入口 
187     curp.x = 1;
188     curp.y = 1;
189     int curstep = 1;//被探索的步数 
190     do
191     {
192         if (pass(curp))
193         {
194             footprint(curp, curstep);//可走就在迷宫里面留下足迹 
195 //创建一个栈元素，存储可行路径的相关值，将这个元素存储到栈当中
196             selement e;
197             e.di = 1;//下一个路块为这一个路块的右边的路块 
198             e.ord = curstep;
199             e.p.x = curp.x;
200             e.p.y = curp.y;
201             push(&path, e);//将路径块入栈 
202 if (curp.x == m - 2 && curp.y == n - 2) break; //如果被压入的路径块到了迷宫的终点就退出循环
203 curp = nextposition(curp, 1);//找到前一个被试块东面的路径块作为被试块
204             curstep++;//被探索的步数加一 
205         }
206         else//如果当前被试路径不能够通过的话 
207         {
208             if (!isstackempty(&path))
209             {
210                 selement e;
211                 pop(&path, &e);
212                 curstep--;
213                 //将所有的周围路径都已经被测试过的路径从栈中清除 
214                 while (e.di == 4 && !isstackempty(&path)) {
215                     markprint(e.p);
216                     pop(&path, &e);
217                     curstep--;
218                 }
219                 //如果当前栈顶还有未被测试的路径就测试剩余的周围路径 
220                 if (e.di<4)
221                 {
222                     curp = nextposition(e.p, e.di + 1);
223                     e.di++;
224                     curstep++;
225                     push(&path, e);
226                 }
227             }
228         }
229     } while (!isstackempty(&path));
230     printf("\n");
231     //打印出结果迷宫矩阵 
232     display_migong();
233     return 0;
234 }