求迷宫的最短路径

Question

1、问题描述

迷宫问题是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。

我们要解决的是如何找到一条迷宫的最短路径。

2、基本要求

（1）设计数据结构存储迷宫；

（2）设计存储结构保存从入口到出口的通路；

（3）设计算法完成迷宫问题的求解；

（4）分析算法的时间复杂度。

3．设计要求

（1）界面友好，函数功能要划分好

（2）总体设计应画一流程图

（3）程序要加必要的注释

（4）要提供程序测试方案，程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

Answer 1

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现
用的是深度优先的算法，可以寻找到走出迷宫的路径

但本题要求求出最短的路径，这就要使用广度优先的算法
一般在程序中需要用到先进先出的队列数据结构

下面是程序的代码，主要原理是用到
quei，quej和prep三个数组来构成队列
分别储存路径的行，列坐标和上一个节点在队列中的位置

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

首先是第一个节点进入队列
当队列不空（循环1）
｛
遍历队列中每节点(循环2）
｛
将八个方向能够走的节点加入队列（循环3）
｝

旧的节点出列
｝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

#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];//<a href="https://www.baidu.com/s?wd=%E6%96%B0%E5%9D%90%E6%A0%87&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1Y4P1nvPHFWuHbzmvNbmh7b0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6KdThsqpZwYTjCEQLGCpyw9Uz4Bmy-bIi4WUvYETgN-TLwGUv3EnHRLPjm3nH0knjDdPWR4PH6vn0" target="_blank" class="baidu-highlight">新坐标</a>
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;
}