用栈求解迷宫问题的所有路径及最短路径程序（纯c语言）-Toy模板网

这篇具有很好参考价值的文章主要介绍了用栈求解迷宫问题的所有路径及最短路径程序（纯c语言）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考了这个博客

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

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

~~----------------------------------------------------------------------------------------~~

正文

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

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

再定义一下栈

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

这里面主要的就是di探索方向用栈求解迷宫问题的所有路径及最短路径程序（纯c语言）

实现试探的代码如下采用了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 +1< min)//比较路径长度
			{
				min = s->top+1;//长度
				_min = count;//最短长度对应的第几条路
			}

完整代码如下

#include<stdio.h>
#define maxsize 100
int 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 +1< min)//比较路径长度
			{
				min = s->top+1;//长度
				_min = count;//最短长度对应的第几条路
			}
			printf("第%d条路径如下：\n", count++);
			for (k = 0; k <= s->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 < 4 && !find)//找下一个可走方块
		{
			di++;//初值为-1
			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;
			}
			if (mg[a][b] == 0)
				find = true;//找到可走方块(a,b)
		}
		if (find)//找到
		{
			s->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;
}

结果示例

用栈求解迷宫问题的所有路径及最短路径程序（纯c语言）文章来源地址https://www.toymoban.com/news/detail-411076.html