关于算法:回溯法之迷宫最短路径c实现

56次阅读

共计 2306 个字符，预计需要花费 6 分钟才能阅读完成。

迷宫的算法很多，然而解释原理的却很少，在这里我利用本人的亲身经历来解说一下求解迷宫的原理

迷宫求解能够利用栈构造，即深度优先，摸索一个地位就标记，通则走
不通则后退寻找下一个地位，能够求出通路，简略然而不肯定是最短门路
这里求最短门路利用的是广度优先的思维，什么是广度优先，利用队列实现，一个元素出队
而后拜访这个元素相邻的所有元素，原理是，一个二维数组，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：这是集体学习过程中得领会，如果有谬误得中央，欢送留言揭示，定会及时批改，如果感觉有帮忙，能够加个关注，前面还会有其余算法得原理剖析和代码，也可私聊我哦

正文完