用栈和队列分别实现求解迷宫问题（c++，c）

求解迷宫问题：给定一个迷宫要求输出其路径。

给出的迷宫如下（可自行更改）

可用两种方法实现1.栈2.队列

用栈只能找到路但路不是最简的最简的要用队列实现

用栈实现（解析都在代码里了）

c++（实现）

记得要给迷宫加个边防止访问越界

//用栈求解迷宫问题
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define M 8
#define N 8
int mg[M+2][N+2]=
{	
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};
//---------------------------------------------------------
//--迷宫栈基本运算---------------------------------------
//---------------------------------------------------------
typedef struct
{
	int i;				//当前方块的行号
	int j;				//当前方块的列号
	int di;				//di是下一可走相邻方位的方位号
} Box;
typedef struct
{
	Box data[MaxSize];	//存放方块
    int top;			//栈顶指针
} StType;				//定义栈类型

void InitStack(StType *&s)		//初始化栈
{	s=(StType *)malloc(sizeof(StType));
	s->top=-1;
}
void DestroyStack(StType *&s)	//销毁栈
{
	free(s);
}
bool StackEmpty(StType *s)		//判断栈是否为空
{
	return(s->top==-1);
}
bool Push(StType *&s,Box e)	//进栈元素e
{
	if (s->top==MaxSize-1)
		return false;
	s->top++;
	s->data[s->top]=e;
	return true;
}
bool Pop(StType *&s,Box &e)	//出栈元素e
{
	if (s->top==-1)	
		return false;
	e=s->data[s->top];
	s->top--;
	return true;
}
bool GetTop(StType *s,Box &e)	//取栈顶元素e
{
	if (s->top==-1)	
		return false;
	e=s->data[s->top];
	return true;
}
//---------------------------------------------------------
bool mgpath(int xi,int yi,int xe,int ye)	//求解路径为:(xi,yi)->(xe,ye)
{
	Box path[MaxSize], e;
	int i,j,di,i1,j1,k;
	bool find;
	StType *st;								//定义栈st
	InitStack(st);							//初始化栈顶指针
	e.i=xi; e.j=yi;	e.di=-1;				//设置e为入口
	Push(st,e);								//方块e进栈
	mg[xi][yi]=-1;							//入口的迷宫值置为-1避免重复走到该方块
	while (!StackEmpty(st))					//栈不空时循环
	{
		GetTop(st,e);						//取栈顶方块e
		i=e.i; j=e.j; di=e.di;
		if (i==xe && j==ye)					//找到了出口,输出该路径
		{ 
			printf("一条迷宫路径如下:\n");
			k=0;							//累计路径中的方块个数 
			while (!StackEmpty(st))
			{
				Pop(st,e);					//出栈方块e
				path[k++]=e;				//将e添加到path数组中
			}
			while (k>0)
			{
				printf("\t(%d,%d)",path[k-1].i,path[k-1].j);
				if ((k+1)%5==0)				//每输出每5个方块后换一行
					printf("\n");  
				k--;
			}
			printf("\n");
			DestroyStack(st);				//销毁栈
			return true;					//输出一条迷宫路径后返回true
		}
		find=false;//最难想到的一步
		while (di<4 && !find)				//找相邻可走方块(i1,j1)
		{	
			di++;
			switch(di)
			{
			case 0:i1=i-1; j1=j;   break;
			case 1:i1=i;   j1=j+1; break;
			case 2:i1=i+1; j1=j;   break;
			case 3:i1=i;   j1=j-1; break;
			}
			if (mg[i1][j1]==0) find=true;	//找到一个相邻可走方块，设置find我真
		}
		if (find)							//找到了一个相邻可走方块(i1,j1)
		{	

			st->data[st->top].di=di;		//修改原栈顶元素的di值
			e.i=i1; e.j=j1; e.di=-1;
			Push(st,e);						//相邻可走方块e进栈
			mg[i1][j1]=-1;					//(i1,j1)的迷宫值置为-1避免重复走到该方块
		}
		else								//没有路径可走,则退栈
		{	
			Pop(st,e);						//将栈顶方块退栈
			mg[e.i][e.j]=0;					//让退栈方块的位置变为其他路径可走方块
		}
	}
	DestroyStack(st);						//销毁栈
	return false;							//表示没有可走路径,返回false
}
int main()
{
	mgpath(1,1,M,N);
	return 1;
}

c实现：

#define  _CRT_SECURE_NO_WARNINGS 1
//顺序栈
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define M 8
#define N 8
int mg[M + 2][N + 2] =
{
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
	int i;
	int j;
	int di;
}Box;
typedef Box ElemType;
typedef struct
{
	ElemType data[100];
	int top;
}SqStack;
SqStack* InitStack()
{
	SqStack* s = (SqStack*)malloc(sizeof(SqStack));
	s->top = -1;
	return s;
}
void DestroyStack(SqStack* s)
{
	free(s);
}
bool StackEmpty(SqStack* s)
{
	return (s->top == -1);
}
bool Push(SqStack* s, ElemType e)
{
	if (s->top == 100 - 1)
		return false;
	s->top++;
	s->data[s->top] = e;
	return true;
}
bool Pop(SqStack* s, ElemType* e)
{
	if (s->top == -1) return false;
	*e = s->data[s->top];
	s->top--;
	return true;
}
bool GetTop(SqStack* s, ElemType* e)
{
	if (s->top == -1) return false;
	*e = s->data[s->top];
	return true;
}
bool mgpath(int xi, int yi, int xe, int ye)
{
	SqStack* st = InitStack();
	Box path[100];
	Box e;
	Box* p = &e;
	e.i = xi, e.j = yi, e.di = -1;
	Push(st, *p);
	mg [xi][yi] = -1;
	int i, j;//存储当前的坐标
	int k = 0;
	int di = -1;
	int ix=0, jy=0;
	bool find=false;
	while (!StackEmpty(st))
	{
		GetTop(st, p);
		i = p->i, j = p->j;
		di = p->di;
		if (i == xe && j == ye)
		{
			printf("路线为\n");
			while (!StackEmpty(st))
			{
				Pop(st, p);
				path[k++] = *p;
			}
			while (k > 0)
			{
				printf("(%d,%d) ", path[k - 1].i, path[k - 1].j);
				k--;
				if ((k+2) % 5 == 0) printf("\n");
			}
			DestroyStack(st);
			return true;
		}
		find = false;
		while (di < 4&&!find)
		{
			di++;
			switch (di)
			{
			case 0:
				{
					ix = i - 1, jy = j;
					break;
				}
			case 1:
				{
					ix = i, jy = j + 1;
					break;
				}
			case 2:
				{
					ix = i + 1, jy = j;
					break;
				}
			case 3:
				{
					ix = i, jy = j - 1;
					break;
				}

			}
			if (mg[ix][jy] == 0) find = true;
			
		}
		if (find)
		{
			e.i = ix, e.j = jy, e.di = -1;
			st->data[st->top].di = di;
			Push(st, *p);
			mg[ix][jy] = -1;
		}
		else
		{
			Pop(st, p);
			mg[p->i][p->j] = 0;
		}
	}
	DestroyStack(st);
	return false;
	
}
int main()
{
	if (!mgpath(1, 1, M, N))
		printf("无解\n");
	return 0;
}

用队列实现

c++实现：

//用队列求解迷宫问题
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define M 8
#define N 8
int mg[M+2][N+2]=
{	
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};
//----------------------------------------------------------
//-非环形队列的基本运算算法---------------------------------
//----------------------------------------------------------
typedef struct 
{	int i,j;						//方块的位置
	int pre;						//本路径中上一方块在队列中的下标
} Box;								//方块类型
typedef struct
{
	Box data[MaxSize];
	int front,rear;					//队头指针和队尾指针
} QuType;							//顺序队类型


void InitQueue(QuType *&q)			//初始化队列
{	q=(QuType *)malloc (sizeof(QuType));
	q->front=q->rear=-1;
}
void DestroyQueue(QuType *&q)		//销毁队列
{
	free(q);
}
bool QueueEmpty(QuType *q)			//判断队列是否为空
{
	return(q->front==q->rear);
}
bool enQueue(QuType *&q,Box e)		//进队列
{	if (q->rear==MaxSize-1)			//队满上溢出
		return false;				//返回假
	q->rear++;						//队尾增1
	q->data[q->rear]=e;				//rear位置插入元素e
	return true;					//返回真
}
bool deQueue(QuType *&q,Box &e)	//出队列
{	if (q->front==q->rear)			//队空下溢出
		return false;
	q->front++;
	e=q->data[q->front];
	return true;
}
//----------------------------------------------------------

void dispapath(QuType *qu,int front)	//从队列qu找到一条迷宫路径并输出
{
	Box path[MaxSize]; 
	int p=front,k=0,i;
	while(p!=-1)							//搜索反向路径path[0..k-1]
	{
		path[k++]=qu->data[p];
		p=qu->data[p].pre;
	}
	printf("一条迷宫路径如下:\n");
	for(i=k-1;i>=0;i--) 					//反向输出path构成正向路径
	{
		printf("\t(%d,%d)",path[i].i,path[i].j);
		if ((k-i)%5==0) printf("\n");		//每输出每5个方块后换一行
	}
	printf("\n");
}
bool mgpath1(int xi,int yi,int xe,int ye)	//搜索路径为:(xi,yi)->(xe,ye)
{
	Box e;
	int i,j,di,i1,j1;
	QuType *qu;						//定义顺序队指针qu
	InitQueue(qu);					//初始化队列qu
	e.i=xi; e.j=yi; e.pre=-1;
	enQueue(qu,e);					//(xi,yi)进队
	mg[xi][yi]=-1;					//将其赋值-1,以避免回过来重复搜索
	while (!QueueEmpty(qu))			//队不空且循环
	{	
		deQueue(qu,e);				//出队方块e,非环形队列中元素e仍在队列中
		i=e.i; j=e.j;
		if (i==xe && j==ye)			//找到了出口,输出路径
		{	
			dispapath(qu,qu->front);	//调用dispapath函数输出路径
			DestroyQueue(qu);		//销毁队列
			return true;			//找到一条路径时返回真
		}
		for (di=0;di<4;di++)		//循环扫描每个方位,把每个可走的方块插入队列中
		{	
			switch(di)
			{
			case 0:i1=i-1; j1=j;   break;
			case 1:i1=i;   j1=j+1; break;
			case 2:i1=i+1; j1=j;   break;
			case 3:i1=i;   j1=j-1; break;
			}
			if (mg[i1][j1]==0)
			{
				e.i=i1; e.j=j1; 
				e.pre=qu->front;	//指向路径中上一个方块的下标
				enQueue(qu,e);		//(i1,j1)方块进队
				mg[i1][j1]=-1;		//将其赋值-1,以避免回过来重复搜索
			}
		}
     }
	DestroyQueue(qu);			//销毁队列
	return false;				//未找到任何路径时返回假
}
int main()
{
	mgpath1(1,1,M,N);
	return 1;
}

c实现

#define  _crt_secure_no_warnings 1
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
//求解迷宫问题
#define m 8
#define n 8
#define maxsize 2000
int ma[m+2][n+2] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,1,0,0,0,1,0,1},
	{1,0,0,0,0,1,1,0,0,1},
	{1,0,1,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,0,0,0,1},
	{1,0,1,0,0,0,1,0,0,1},
	{1,0,1,1,1,0,1,1,0,1},
	{1,1,0,0,0,0,0,0,0,1},
	{1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
	int i, j;//当前坐标
	int pre;//前一个步在队列中的下标
	int di;
}box;//每一个结点的数据
typedef struct
{
	box data[maxsize];
	int front, rear;	
}sqqueue;
sqqueue* initqueue()
{
	sqqueue* s = (sqqueue*)malloc(sizeof(sqqueue));
	s->front = s->rear = -1;
	return;
}
bool enqueue(sqqueue* s, box e)
{
	if (s->rear == maxsize - 1) return false;
	s->rear++;
	s->data[s->rear] = e;
	return true;
}
bool queueempty(sqqueue* s)
{
	return (s->front == s->rear);
}
bool dequeue(sqqueue* s, box* e)
{
	if (s->front == s->rear) return false;
	s->front++;
	*e = s->data[s->front];
	return true;
}
void destroyqueue(sqqueue* s)
{
	free(s);
}
bool mgpath(int xi, int yi, int xe, int ye)
{
	void print(sqqueue * s, int front);
	int front;
	sqqueue* s = initqueue();
	box* e = (box*)malloc(sizeof(box));
	int i=0, j=0, di=-1;
	e->i = xi, e->j = yi, e->di = -1,e->pre = -1;
	int i1=0, j1=0;
	enqueue(s,*e);
	ma[xi][yi] = -1;
	while (!queueempty(s))
	{
		dequeue(s, e);
		i = e->i, j = e->j;
		di = e->di;
		if (i == xe && j == ye)
		{
			printf("迷宫路径如下:\n");
			print(s,s->front);
			return true;
		}
		while (di < 3)
		{
			di++;
			switch (di)
			{
			case 0:i1 = i - 1; j1 = j; break;
			case 1:i1 = i; j1 = j + 1; break;
			case 2:i1 = i + 1; j1 = j; break;
			case 3:i1 = i; j1 = j - 1; break;
			}
			if (!ma[i1][j1])
			{
				e->i = i1, e->j = j1, e->di =-1, e->pre = s->front;
				enqueue(s, *e);
				ma[i1][j1] = -1;
			}
		}
	}
	destroyqueue(s);
	return false;
}
void print(sqqueue* s,int front)
{
	box path[maxsize];
	int p = front, k = 0;
	int i;
	while (p != -1)
	{
		path[k++] = s->data[p];
		p = s->data[p].pre;
	}
	for (i = k - 1; i >= 0; i--)
	{
		printf("\t(%d,%d) ", path[i].i, path[i].j);
		if ((k - i) % 5 == 0) printf("\n");
	}
	printf("\n");
}
int main()
{
	if (!mgpath(1, 1, 8, 8)) printf("此迷宫无解\n");
	return 0;

}

总结：

总结此题利用队列和栈的特点来解决，需要对栈和队列有一定的理解，如果还没学到栈和队列的话建议学完再完成。

最后给（本蒟蒻）点个赞哒