一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径
但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构
下面是程序的代码，主要原理是用到
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;
}