Question

迷宫最短路径（c语言编程）

实 验 二 迷宫最短路径
题目：迷宫最短路径

⒈问题描述

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

⒉基本要求

(1) 输入数据

a.输入迷宫的大小m行和n列，两者为整数

b. 由随机数产生0或1，建立迷宫。

(2) 输出数据

首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示： (m，n)， ……， (i，j)， ……， (1，1)

如无通道，则打印：

THERE IS NO PATH.

⒊实现提示

(1) 数据结构

a）为了在程序中判断方便，把迷宫扩展成为MAZE(0..m+1，0..n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。

b）用二维数组MOVE(1..8，1..2)存放八个方向上的位置量，如图所示：

(i+MOVE[1，1]， j+MOVE[1，2])

(i+MOVE[8，1]， j+MOVE[8，2]) (i+MOVE[1，1]， j+MOVE[1，2])

(i+MOVE[7，1]， j+MOVE[7，2]) (i+MOVE[3，1]， j+MOVE[3，2])

(i+MOVE[6，1]， j+MOVE[6，2]) (i+MOVE[4，1]， j+MOVE[4，2])

(i+MOVE[5，1]， j+MOVE[5，2])

MOVE的设置情况

i j

1

2

1
-1
0

2
-1
1

3
0
1

4
1
1

5
1
0

6
1
-1

7
0
-1

8
-1
-1

c) 为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK（i，j）置为为1。

d) 为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1， 0..2）数组，对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置i和j，Q(P，2)记下其出发点在Q数组中的下标。

（2）算法基本思想

将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。

具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(i，j)=0 且MARK(i，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m ，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。

Answer 1

我帮你做吧。。给我一点时间。。做不出来我会吱一声的。。