C++迷宫寻路，利用顺序队，在迷宫中寻找一条从起点到终点的路。

C++迷宫寻路，利用顺序队，在迷宫中寻找一条从起点到终点的路。

因为用到队列解决问题，如果考虑到这个，必须要掌握队列的知识。所以关于队列的代码不多讲解。

迷宫寻路，算法的简单描述：
首先将起点保存到路类型的数组中，pre赋值负一，弹出起点路（因为不是环形队列，出队后仍在队列中（如果不明白可参考环形队列和顺序队的结构）），从起点开始上左下右的寻找路，找到可走的路之后保存到路类型的数组中，弹出最初找到的第一个路（非起点），然后寻找这个弹出的路的上左下右可走的路，然后保存到路类型的数组中，如此循环…如果这个弹出的路是终点，则触发if，输出我们的路径，至于输出要用我们自己改写的print函数，详细看print函数的功能。如果队列为空，则是未找到路径，结束函数，输出未找到路径的提示语。

队列函数
如果记不起他们的作用，可在总代码中查看他们的详细。

void InitQueue(QuType*& q);//初始化队列bool QueueEmpty(QuType* q);//判断队列是否为空bool enQueue(QuType*& q, Box e);//加入队列bool deQueue(QuType*& q, Box& e);//离开队列void DestroyQueue(QuType*& q);//销毁队列

print函数（我们自己改写的）
作用为输出队列中符合条件的方块（路）

void print(QuType* qu, int front)//我们自己重写的print函数
{                                //作用是输出qu里的路径int k = front, j, ns = 0;cout << endl;//换行do//do-while{j = k;//do-while先赋值一次再循环k = qu->data[k].pre;//赋值给k当前方块的前一个方块的下标qu->data[j].pre = -1;//将当前方块的pre设为-1} while (k != 0);//pre在输出的时候可作为标记，在寻路的时候是当前方块的上一个方块的下标cout << "一条迷宫路径如下：" << endl;k = 0;while (k <= front)//当k小于front时（可以考虑下为什么）{if (qu->data[k].pre == -1)//输出所有pre=-1的方块坐标{ns++;//为排版而存在的变量cout << "(";cout << qu->data[k].i;cout << ",";cout << qu->data[k].j;cout << ")";//输出坐标if (ns % 5 == 0)//五个一行cout << endl;}k++;}cout << endl;//换行
}

mgpath1函数，本次的寻路函数

bool mgpath1(int xi, int yi, int xe, int ye)//xiyi为出发点的xy，xeye为终点的xy
{Box e;//Box类型的eint i, j, di, i1, j1;QuType* qu;//队列指针InitQueue(qu);//初始化e.i = xi; e.j = yi; e.pre = -1;//赋值出发点enQueue(qu, e);//盒子进队mg[xi][yi] = -1;//出发点赋值-1while (!QueueEmpty(qu))//当队列不空时循环{deQueue(qu, e);//出队e，因为不是环形队列，出队后e仍在队列中。i = e.i; j = e.j;//赋值e的位置if (i == xe && j == ye)//如果e的位置是终点{print(qu, qu->front);//调用print函数（我们自己重写的函数）DestroyQueue(qu);//销毁队列return true;//返回真}for (di = 0; di < 4; di++)//四个方位循环扫描{switch (di)//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)//如果这个点为0（路）{e.i = i1; e.j = j1;//可走的话将这个添加到e中e.pre = qu->front; //e的pre指向上一个方块的下标enQueue(qu, e);//进队mg[i1][j1] = -1;//赋值该方块为-1表示不可再走}}}DestroyQueue(qu);//销毁队列return false;//返回假，表示没有找到路径
}

放一下我们的迷宫变量

int mg[M + 2][N + 2] = {//迷宫 1是墙壁 0是路  +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}
};

最后放一下我们很简单的主函数

int main() {if (!mgpath1(1, 1, M, N))//调用mgpath1函数，为真则无解cout << "该迷宫问题没有解！" << endl;return 1;
}

总代码：

#include 
using namespace std;const int MaxSize = 100;//足够大，最小等于路的个数（如果不明白可等明白该算法原理再回头看看）
const int M = 8;//迷宫大小（左右长）
const int N = 8;//迷宫大小（上下长）typedef struct
{int i, j;//方块的位置int pre;//本路径中上一个方块在队列中的下标
}Box;//方块数据类型typedef struct
{Box data[MaxSize];//方块类型的数组int front, rear;//队头指针和队尾指针
}QuType;//顺序队类型void InitQueue(QuType*& q);//初始化队列bool QueueEmpty(QuType* q);//判断队列是否为空bool enQueue(QuType*& q, Box e);//加入队列bool deQueue(QuType*& q, Box& e);//离开队列void DestroyQueue(QuType*& q);//销毁队列void print(QuType* qu, int front);//打印队列int mg[M + 2][N + 2] = {//迷宫 1是墙壁 0是路  +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}
};bool mgpath1(int xi, int yi, int xe, int ye)//xiyi为出发点的xy，xeye为终点的xy
{Box e;//Box类型的eint i, j, di, i1, j1;QuType* qu;//队列指针InitQueue(qu);//初始化e.i = xi; e.j = yi; e.pre = -1;//赋值出发点enQueue(qu, e);//盒子进队mg[xi][yi] = -1;//出发点赋值-1while (!QueueEmpty(qu))//当队列不空时循环{deQueue(qu, e);//出队e，因为不是环形队列，出队后e仍在队列中。i = e.i; j = e.j;//赋值e的位置if (i == xe && j == ye)//如果e的位置是终点{print(qu, qu->front);//调用print函数（我们自己重写的函数）DestroyQueue(qu);//销毁队列return true;//返回真}for (di = 0; di < 4; di++)//四个方位循环扫描{switch (di)//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)//如果这个点为0（路）{e.i = i1; e.j = j1;//可走的话将这个添加到e中e.pre = qu->front; //e的pre指向上一个方块的下标enQueue(qu, e);//进队mg[i1][j1] = -1;//赋值该方块为-1表示不可再走}}}DestroyQueue(qu);//销毁队列return false;//返回假，表示没有找到路径
}void print(QuType* qu, int front)//我们自己重写的print函数
{                                //作用是输出qu里的路径int k = front, j, ns = 0;cout << endl;//换行do//do-while{j = k;//do-while先赋值一次再循环k = qu->data[k].pre;//赋值给k当前方块的前一个方块的下标qu->data[j].pre = -1;//将当前方块的pre设为-1} while (k != 0);//pre在输出的时候可作为标记，在寻路的时候是当前方块的上一个方块的下标cout << "一条迷宫路径如下：" << endl;k = 0;while (k <= front)//当k小于front时（可以考虑下为什么）{if (qu->data[k].pre == -1)//输出所有pre=-1的方块坐标{ns++;//为排版而存在的变量cout << "(";cout << qu->data[k].i;cout << ",";cout << qu->data[k].j;cout << ")";//输出坐标if (ns % 5 == 0)//五个一行cout << endl;}k++;}cout << endl;//换行
}int main() {if (!mgpath1(1, 1, M, N))//调用mgpath1函数，为真则无解cout << "该迷宫问题没有解！" << endl;return 1;
}void InitQueue(QuType*& q)//初始化队列
{q = (QuType*)malloc(sizeof(QuType));q->front = q->rear = -1;
}bool QueueEmpty(QuType* q)//队列是否为空
{return(q->front == q->rear);
}bool enQueue(QuType*& q, Box e)//进队
{if (q->rear == MaxSize - 1)return false;q->rear++;q->data[q->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 DestroyQueue(QuType*& q)//销毁队列
{free(q);
}

遗留问题：没有寻找迷宫中所有可行的路径，没有考虑路径是否最短。功能仅为寻找一条路线。

结构数据教程（第五版）-清华大学出版社
https://blog.csdn.net/sxhelijian/article/details/48465491 数据结构例程——迷宫问题（用队列）

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！