栈的简单应用-迷宫问题

　                                             迷宫问题

　　迷宫问题一直是计算机工作者感兴趣的问题，因为它可以展现栈的巧妙应用，

这里将利用栈开发一个走迷宫程序，虽然在发现正确路径前，程序要尝试许多

错误路径，但是，一旦发现，就能够重新走出迷宫，而不会再去尝试任何错误路径。

                                                迷宫问题求解

       计算机中可以用如图所示的方块图表示迷宫。图中空白方块为通道，蓝色方块为墙

  

 

       迷宫的储存可以使用二维数组，其中“0”代表墙值，“1”代表通路。由于迷宫被表示为

二维数组，所以，在任何时刻，迷宫中的位置都可以用行，列坐标来描述。

       在迷宫中的某一个位置进行移动的可能方向如图所示

  

 

       值得注意的是，并不是每一个位置都有四个邻居。如果[row][col]在边界上那么邻居的

个数就少于4个，甚至只有2个。为了避免边界条件的检查，在迷宫周围加上一圈边界。这样，

一个m*n的迷宫就需要一个(m+2)*(n+2)的数组。入口位置在[1][1],而出口位置在[m][n]。

       另一个简化问题的策略是，用数值direc 预先定义出“可能的移动方向”数字0-3表示4个

可能的移动方向，对每个方向都指出其垂直和水平的偏移量。

     

　

 

 

　　求迷宫中一条径的算法的基本思想是：

若当前位置“可通“，则纳入”当前路径”，并继续朝“下一个位置探索”，即切换“下一位置”为

“当前位置”，如此反复直到出口；

若当前位置“不可通”则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；

若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。假设以栈

s记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，

“纳入路径”的操作即为“当前位置压入”，“从当前路径上删除前一块通道块”的操作即为“弹出”。

需要说明的是，所谓的当前位置可通，指的是未曾走到过的通道块，即要求该方块位置s记录“当前路径”，

则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置压入”，

“从当前路径上删除前一块通道块”的操作即为“弹出”。不仅是通道块，而且不在当前路径上(否则路径不是简单路径)，

也不是曾经纳入过路径的通道块(否则只能在死胡同内转圈)。

　sqstack.h  

 1 #pragma once
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #define stack_init_size 100//储存空间初始分配量
 5 #define stackincrement  10//存储空间分配增量
 6 #define ok 1
 7 #define error 0
 8 typedef struct {
 9     int x;  //行值
10     int y;  //列值
11 }postype;  //迷宫坐标位置类型
12 typedef struct 
13 {
14     int ord;      //序号
15     int di;       //方向
16     postype seat; //位置  
17 
18 } stacktype; //栈元素类型
19 
20 typedef struct {
21     stacktype *base;   //在构造之前和销毁之后，base的值为null
22     stacktype *top;    //栈顶指针
23     int stacksize;     //当前已分配的存储空间，以元素为单位
24     
25 }sqstack; //顺序栈
26 
27 //栈的初始化
28 int initstack(sqstack *p) {
29 
30 
31     p->base = (stacktype*)malloc(stack_init_size * sizeof(stacktype));
32     if (p->base == null)  return error;  //内存分配失败
33     p->top = p->base;     //栈顶与栈底相同表示一个空栈
34     p->stacksize = stack_init_size;
35     return ok;
36 
37 }
38 //判断栈是否为空
39 int emptystack(sqstack *p) {
40     //若为空栈 则返回ok，否则返回error
41     if (p->top == p->base) return ok;
42     else return error;
43 }
44 //顺序栈的压入
45 int push(sqstack *p, stacktype e) {
46     //插入元素e为新的栈顶元素
47     if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间
48     {
49         p->base = (stacktype*)realloc(p->base, (p->stacksize + stackincrement) * sizeof(stacktype));
50         if (p->base == null)   return error;// 储存空间分配失败
51         p->top = p->base + p->stacksize;   
52         p->stacksize += stackincrement;
53     }
54     *(p->top) = e;
55     (p->top)++;
56     return ok;
57 }
58 // 顺序栈的弹出     
59 int pop(sqstack *p, stacktype *e) {
60     //若栈不空，则删除p的栈顶元素，用e返回其值
61     if (p->top == p->base) return error;
62     --(p->top);
63     *e = *(p->top);
64     return ok;
65 
66 
67 }
68 //将顺序栈置空 栈还是存在的，栈中的元素也存在，
69 //如果有栈中元素的地址任然能调用
70 int clearstack(sqstack *p) {
71     p->top = p->base;
72     return ok;
73 }
74 //顺序栈的销毁
75 int destroystack(sqstack *p) {
76     //释放栈底空间并置空
77     free(p->base);
78     p->base = null;
79     p->top = null;
80     p->stacksize = 0;
81 
82     return ok;
83 }

　　源代码：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "sqstack.h" //引入顺序栈储存结构及其基本操作
  4 #define maxlength 25  //设迷宫最大行列为25
  5 #define error 0
  6 #define ok 1
  7 #define true 1
  8 #define false 0
  9 typedef int status;
 10 typedef int mazetype[maxlength][maxlength]; //迷宫数组[行][列]
 11 postype begin, end;   //迷宫入口坐标，出口坐标
 12 postype direc[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}，移动方向依次为东南西北
 13 mazetype maze; //迷宫数组
 14 int x, y;//迷宫的行，列
 15 int curstep = 1;  //当前足迹，初值在入口处为1
 16 struct selemtype
 17 {
 18     int ord;  //通道块在路径上的“序号”
 19     postype seat;   //通道块在迷宫中的“坐标位置”
 20     int di;  //从此通道块走向下一通道块的“方向”(0-3表示东-北)
 21 };
 22 void print() {
 23     //输出迷宫结构
 24     int i, j;
 25     for (i = 0; i < x; i++)
 26     {
 27         for (j = 0; j < y; j++)
 28             printf("%3d", maze[i][j]);
 29         printf("\n");
 30     }
 31 }
 32 void init()
 33 {
 34     //设定迷宫布局(墙值为0，通道值为1)
 35     //全局变量maze 未初始化 所以均为值均为0
 36     int i, j, x1, y1;
 37     printf("请输入迷宫的行数，列数(包括外墙):");
 38     scanf("%d%d", &x, &y);
 39     for (i = 1; i < x - 1; i++)
 40         for (j = 1; j < y - 1; j++)
 41             maze[i][j] = 1;  //定义通道初值为1
 42     printf("请输入迷宫内墙单元数:");
 43     scanf("%d", &j);
 44     printf("请依次输入迷宫内墙每个单元的行数，列数:\n");
 45     //file *fp; 注释掉的这五行之前是方便我调试的
 46     //fp = fopen("maze.txt", "r");
 47     //int *px1 = &x1, *py1 = &y1;
 48     for(i=1;i<=j;i++)
 49     {
 50         //fscanf(fp, "%d%d", px1, py1);
 51         //maze[x1][y1] = 0;
 52         scanf("%d%d", &x1, &y1);
 53         maze[x1][y1] = 0; //定义墙值为0
 54     }
 55     printf("迷宫结构如下:\n");
 56     print();
 57     printf("请输入入口的行数，列数:");
 58     scanf("%d%d", &begin.x, &begin.y);
 59     printf("请输入出口的行数，列数:");
 60     scanf("%d%d", &end.x, &end.y);
 61 }
 62 void markprint(postype seat)
 63 {//标记迷宫块不可通过
 64     maze[seat.x][seat.y] = -1;
 65     
 66 
 67 }
 68 status pass(postype b)
 69 {
 70     //当迷宫m的b点的值为1，return ok;
 71     //否则return error;
 72     if (maze[b.x][b.y] == 1)
 73         return ok;
 74     else
 75         return error;
 76 }
 77 void footprint(postype b)
 78 {
 79 //使迷宫m的b点的值变为足迹(curstep),表示经过
 80     maze[b.x][b.y] = curstep;
 81 
 82 }
 83 postype nextpos(postype  b,int di)
 84 {
 85     //根据当前位置b及其移动方向di，修改b为下一位置
 86     b.x += direc[di].x;
 87     b.y += direc[di].y;
 88     return b;
 89 }
 90 status mazepath(postype start, postype end)
 91 {
 92     //若迷宫m中存在从入口start到出口end的通道
 93     //则求得一条存放在栈中，并返回true；否则返回false
 94     sqstack s,*s; //顺序栈
 95     s = &s;
 96     postype curpos;
 97     stacktype e,*pe;
 98     pe = &e;
 99     initstack(s);
100     curpos = start;
101     do
102     {
103         if (pass(curpos)) //当前可以通过，则是未曾走到的通道块
104         {
105             footprint(curpos); //留下足迹
106             e.ord = curstep;  //栈元素序号为当前序号
107             e.seat = curpos;  //栈元素位置为当前位置
108             e.di = 0;  //从当前位置出发，下一位置为东
109             push(s, e); //入栈当前位置及其状态
110             curstep++;   //足迹加1
111             if (curpos.x == end.x&&curpos.y == end.y)  //到达出口
112                 return true;
113             curpos = nextpos(curpos, e.di); //由当前位置及移动方向确定下一个当前位置
114         }
115         else //当前位置不能通过
116             if (!emptystack(s))  //栈不为空
117             {
118                 pop(s, pe); // 退栈到前一位置
119                 curstep--;  //足迹减1
120                 while (e.di == 3 && !emptystack(s))  //前一位置处于最后一个方向(北)
121                 {
122                     markprint(e.seat); //留下不能通过的标记(-1)
123                     pop(s, pe); //退一步
124                     curstep--; //足迹再减1
125 
126                 }
127                 if (e.di < 3)  //没有到最后一个方向(北)
128                 {
129                     e.di++;  //换下一个方向探索
130                     push(s, e); //入栈该位置的下一个方向
131                     curstep++;// 足迹加1
132                     curpos = nextpos(e.seat, e.di);
133 
134                 }
135 
136             }
137 
138     }
139     while (!emptystack(s));
140     return false;
141     
142     
143 }
144 int main() 
145 {
146     init();  //初始化迷宫
147     if (mazepath(begin, end)) //有通路
148     {
149         printf("从此迷宫入口到出口的一条路径如下:\n");
150         print();
151     }
152     else
153         printf("此迷宫没有从入口到出口的路径\n");
154     return 0;
155 
156     
157 }
158         

  　　测试如下：

　　需要注意的是得到的路径并不是最短路径。要求最短路径应该把所有

路径求出，再比较栈的大小 。最小长度的栈则保存着最短的路径。