求广度优先算法C++走迷宫程序，可以显示路径

Question

最好可以显示路径

Answer 1

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现

用的是深度优先的算法，可以寻找到走出迷宫的路径

但本题要求求出最短的路径，这就要使用广度优先的算法

一般在程序中需要用到先进先出的队列数据结构

下面是程序的代码，主要原理是用到

quei，quej和prep三个数组来构成队列

分别储存路径的行，列坐标和上一个节点在队列中的位置

大致算法如下，右三个嵌套的循环实现

首先是第一个节点进入队列

当队列不空（循环1）

｛

     遍历队列中每节点(循环2）

    ｛

         将八个方向能够走的节点加入队列（循环3）

     ｝

     旧的节点出列

｝

#include<iostream>
#include<ctime> 
using namespace std; 
 
#define MAXNUM 50
 
void main() 
{
    int m,n,i,j,x;
    cout<<"请输入迷宫大小"<<endl;
    cin>>m>>n;
    int maze[MAXNUM][MAXNUM];
     
    srand((int)time(NULL));
    for(i=0;i<=m+1;i++){
        for(j=0;j<=n+1;j++){
            if(i==0||j==0||i==m+1||j==n+1)
                maze[i][j]=1;
            else
            {
            x=rand()%1000;
            if(x>700){maze[i][j]=1;} //控制矩阵中1的个数，太多1迷宫很容易走不通
            else{maze[i][j]=0;}
            }
            cout<<maze[i][j]<<' ';
        }
        cout<<endl;
    }
 
    //以上是输入和迷宫生成，一下是走迷宫
 
 
    int move[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
    int *quei=new int[m*n];//储存行坐标队列
    int *quej=new int[m*n];//储存列坐标队列
    int *prep=new int[m*n];//储存之前一步在队列中的位置
    int head,rear,length;//队列头，队列尾，队列长度
    head=0;rear=1;length=1;
    quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列
 
    int pos;//当前节点在队列中的位置，
    int ii,jj,ni,nj;//当前节点的坐标，新节点的坐标
    int dir;//移动方向
 
    if(maze[1][1]==1)length=0;//第一点就不能通过
    else maze[1][1]=1;
 
 
    while(length)//队列非空继续
    {
        for(pos=head;pos<head+length;pos++)//寻找这一层所有节点
        {
            ii=quei[pos];jj=quej[pos];//当前位置坐标
            if(ii==m&&jj==n)break;
            for(dir=0;dir<8;dir++)//寻找8个方向
            {
                ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标
                if(maze[ni][nj]==0)//如果没有走过
                {
                    quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
                    rear=rear+1;
                    maze[ni][nj]=1;//标记已经走过
                }
            }
        }
        if(ii==m&&jj==n)break;
        head=head+length;
        length=rear-head;//这一层节点出列
    }
 
    if(ii==m&&jj==n)
    {
        while(pos!=-1)
        {
            cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
            pos=prep[pos];
            if (pos!=-1)cout<<',';
        }
    }
    else
    {
        cout<<"THERE IS NO PATH."<<endl;
    }
 
    delete []quei;
    delete []quej;
    delete []prep;
}