参考了这个博客

学校作业，在各种地方搜了半天，看别人的要么就是有点错，要么就是很复杂用了不少我不知道的库，还要么就是只求了一条路径，还要么就是用了c++没学过。

写了半天，写出了一个应该是比较简单的方法，应该是还能优化，不过作业能跑就行，懒得搞了。有更好的想法，欢迎交流。

—————————————————————————————-

正文

讲讲思路吧，首先定义一下迷宫的方块

typedef struct {int i;//行int j;//列int di;//探索方向}box;

再定义一下栈

typedef struct {box data[maxsize];int top;}stack;//定义栈的类型

这里面主要的就是di探索方向

实现试探的代码如下采用了switch的方法

switch (di)//试探方块{case 0:a = i - 1, b = j; break;case 1:a = i, b = j + 1; break;case 2:a = i + 1, b = j; break;case 3:a = i, b = j - 1; break;}

如试探的方块是可以通过的那就入栈，要是所有方向都不行就退栈，回到上一个方块，以此类推，直到试探到方块是出口。同时为了防止重复经过方块，再入栈时把迷宫数组在这一点变成-1（0是路，1是墙）

比较关键的是怎么探查出所有的路径。

我的想法是在第一次找到出口时，在输出路径后，就直接退栈，再利用continue结束这次循环。达到回溯道路的作用。

退栈后回到上一个方块 ，换一个方向再继续试探，重复以上的过程即可。

再就是算最短路径，直接再找到出口的时候比较一下top指针就好了

if (s->top +1top+1;//长度_min = count;//最短长度对应的第几条路}

完整代码如下

#include#define maxsize 100int mg[6][6]={ {1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1} };//设置迷宫 1为墙，0为路typedef struct {int i, j, di;}box;//定义栈的元素typedef struct {box data[maxsize];int top;}stack;//定义栈的类型void Initstack(stack*& s)//初始化栈{s = new stack;s->top = -1;}bool push(stack*& s, box e)//压栈{if (s->top == maxsize - 1)return false;s->top++;s->data[s->top] = e;return true;}bool pop(stack*& s, box &e)//出栈{if (s->top == -1)return false;e = s->data[s->top];s->top--;return true;}bool gettop(stack*& s, box& e) //取栈顶元素{if (s->top == -1)return false;e = s->data[s->top];return true;}bool mgpath(int x, int y, int xi, int yi)//寻找路径 起点坐标(x,y)终点坐标(xi,yi){int min = 100, _min=1;int i, j, di,count=1,k,a,b;int flag = 0;//有解的标志box e;bool find;stack* s;Initstack(s);//初始化栈e.i = x;//设置入口e.j = y;e.di = -1;push(s, e);mg[x][y] = -1;//入口设为-1防止重复走while (s->top != -1)//不为空栈时循环{gettop(s, e);//取栈顶方块e(i,j)i = e.i;j = e.j;di = e.di;if (i == xi && j == yi)//找到出口输出该路径{flag = 1;if (s->top +1top+1;//长度_min = count;//最短长度对应的第几条路}printf("第%d条路径如下：\n", count++);for (k = 0; k top; k++)printf("(%d,%d)\t", s->data[k].i, s->data[k].j);printf("\n");pop(s, e);//回溯道路mg[e.i][e.j] = 0;continue;//结束当次循环}find = false;while (di data[s->top].di = di;e.i = a;e.j = b;e.di = -1;push(s, e);//方块（a，b）入栈mg[a][b] = -1;//设为-1防止重复走}else //找不到{pop(s, e);mg[e.i][e.j] = 0;//恢复退栈方块}}if (flag == 1){printf("最短路径为路径%d\n", _min);printf("最短路径长度为%d\n", min);return true;}delete(s);//释放栈return false;}int main(){if (!mgpath(1, 1, 4, 4))printf("该迷宫问题没有解！\n");return 0;}

结果示例