迷宫问题
迷宫问题一直是计算机工作者感兴趣的问题,因为它可以展现栈的巧妙应用,
这里将利用栈开发一个走迷宫程序,虽然在发现正确路径前,程序要尝试许多
错误路径,但是,一旦发现,就能够重新走出迷宫,而不会再去尝试任何错误路径。
迷宫问题求解
计算机中可以用如图所示的方块图表示迷宫。图中空白方块为通道,蓝色方块为墙
迷宫的储存可以使用二维数组,其中“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
测试如下:
需要注意的是得到的路径并不是最短路径。要求最短路径应该把所有
路径求出,再比较栈的大小 。最小长度的栈则保存着最短的路径。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605475.html