数据结构算法 用C++ 迷宫最短路径

Question

⒈问题描述
从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。

⒉基本要求
输入数据
输入迷宫的大小m行和n列，两者为整数
由随机数产生0或1，建立迷宫。
输出数据
首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：
(m，n)， ……， (I，j)， ……， (1，1)
如无通道，则打印：
THERE IS NO PATH.
⒊实现提示
数据结构
⑴为了在程序中判断方便，把迷宫扩展成为MAZE(0：m+1，0：n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。
⑵用二维数组MOVE(1：8，1：2)存放八个方向上的位置量。

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;
}