回溯法之迷宫最短门路，c++实现
迷宫的算法很多，然而解释原理的却很少，在这里我利用本人的亲身经历来解说一下求解迷宫的原理
- 迷宫求解能够利用栈构造，即深度优先，摸索一个地位就标记，通则走
- 不通则后退寻找下一个地位，能够求出通路，简略然而不肯定是最短门路
- 这里求最短门路利用的是广度优先的思维，什么是广度优先，利用队列实现，一个元素出队
- 而后拜访这个元素相邻的所有元素，原理是，一个二维数组，0示意墙，1示意路，这里我利用随机数生成0和1，4个方向
- 在广度优先算法的思维下，队头元素出队，而后广度顺次拜访他的4个方向，顺次入队，并记下他们的前一个坐标在队列中的地位
- 反复直到出对的是起点，在找到起点后，利用每一个地位都有前一个坐标在队列中的下标进行回访，拜访到终点即走了一遍找到的门路，此时便可正向输入门路即可。
广度优先拜访的过程就是，假如当初队头是5，5出队后，拜访5的相邻元素，行将6，8，4，2入队，这里是顺时针方向，一次类推。
假如这里9个元素全副是路，一开始1入队，而后1出队，拜访周围，2，4顺次入队，前一个坐标是1，2出队，3，5入队，前一个坐标是2，4出队，7入队，前一个坐标是4，3出队，6入队，前一坐标是3，5出队，8入队，前一坐标是8，6出队，9入队，前一坐标是6，拜访了起点9，完结入队，从9开始回访，9->6->3->2->1 即找到最短门路。
#include<iostream>#include<stdlib.h>#include<time.h>using namespace std;struct Node{ int data; int flag;};struct Path { int xpath; int ypath; int pox; //在队列中的下标 }; class Maze { private: int n, m; //迷宫的行和列 Node *maze; //迷宫寄存 Path *que; int top = -1; int front = -1; int rear = -1; public: void create() { int i, j; cout<<"输出迷宫的行和列："; cin>>n>>m; maze = new Node[n*m]; srand(time(NULL)); for(i = 0; i<n; i++) { for(j = 0; j<m; j++) { int temp = rand()%4; if(temp != 1) maze[i*m+j].data = 1; else maze[i*m+j].data = 0; maze[i*m+j].flag = 0; } } maze[0].data = 8; //设置终点 maze[n*m-1].data = 1; show(); } /*搜寻门路*/ void seek_road() /*先实现一个门路先*/ { //path = new Path[n*m]; int x1, y1; que = new Path[n*m]; //利用广度优先实现最短门路 que[0].xpath = 0; que[0].ypath = 0; que[0].pox = 0; maze[0].flag = 1; rear++; while(front != rear) { int x = que[(++front)%(n*m)].xpath; //获取队头的坐标，而后将其周围的通路进队,晓得操作完队尾元素 int y = que[front%(n*m)].ypath; // path[++top] = que[front]; if(judge_head()) return; if(y+1<m) push_road(x,y+1); if(x+1<n) push_road(x+1,y); if(y-1>=0) push_road(x,y-1); if(x-1>=0) push_road(x-1,y); } cout<<"没有通路!!"<<endl; } void show() { for(int i = 0; i<n; i++) { for(int j = 0; j<m; j++) { if(maze[i*m+j].data == 8) cout<<"■ "; else cout<<maze[i*m+j].data<<" "; } cout<<endl; } } int judge_head() { int k=1; if(que[front].xpath == n-1 && que[front].ypath == m-1) { cout<<"找到迷宫的通路！"<<endl; int x = que[front].xpath; int y = que[front].ypath; int t = que[front].pox; //前一个坐标在队列的下标 while(x != 0 || y != 0) { maze[x*m+y].data = 8; x = que[t].xpath; y = que[t].ypath; t = que[t].pox; k++; } show(); cout<<"门路长度为："<<k<<endl; return 1; } return 0; } void push_road(int x, int y) { if(maze[x*m+y].data == 1 && maze[x*m+y].flag == 0) { que[(++rear)%(n*m)].xpath = x; que[rear%(n*m)].ypath = y; que[rear%(n*m)].pox = front; //设置上一个坐标在队列中的地位 maze[x*m+y].flag = 1; } }};int main(){ Maze *ma = new Maze(); /*待解决-迷宫最短门路问题*/ ma->create(); ma->seek_road(); return 0;} ps：这是集体学习过程中得领会，如果有谬误得中央，欢送留言揭示，定会及时批改，如果感觉有帮忙，能够加个关注，前面还会有其余算法得原理剖析和代码，也可私聊我哦