迷宫最短路径（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数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。

做出来了。。花了一天时间。。唉。。下面是代码。。
如果看的麻烦的话。。留个邮箱，我直接把程序文件发过去。。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>


int** CreateTwoDimensionalArr(int a, int b)//动态创建二位数组。。
{
int i;
int **p;
p = (int**)malloc(sizeof(int*) * a);
if (p == NULL)
{
printf("内存分配失败，程序强制退出。。");
exit(1);
}
for (i = 0; i < a; i++)
{
p[i] = (int*)malloc(sizeof(int) * b);
if (p[i] == NULL)
{
printf("内存分配失败，程序强制退出。。");
exit(1);
}
}
return (p);
}


void FreeTwoDimensionalArr(int **p, int a, int b)//释放动态分配的内存。。
{
int i;
for (i = 0; i < a; i++)//释放动态分配的内存。。
{
free(p[i]);
}
free(p);
}


void main()
{
int m;//迷宫行数。。
int n;//迷宫列数。。
int **MAZE;//迷宫。。
int **MARK;//标志。。
int **Q;//记录路线。。
int **RECORD;//记录最短路径。。
int MOVE[9][3] = {2, 2, 2,
2,-1, 0,
2,-1, 1,
2, 0, 1,
2, 1, 1,
2, 1, 0,
2, 1,-1,
2, 0,-1,
2,-1,-1};
int i;
int j;
printf("请输入迷宫的大小：\nm=");
scanf("%d", &m);
printf("n=");
scanf("%d", &n);
int minSteps = m * n;//记录最短路径长度。。
MAZE = CreateTwoDimensionalArr(m + 2, n + 2);
MARK = CreateTwoDimensionalArr(m + 1, n + 1);
Q = CreateTwoDimensionalArr(m * n, 4);
for (j = 0; j < n + 2; j++)//设置迷宫的墙壁。。
{
MAZE[0][j] = 1;
MAZE[m + 1][j] = 1;
}
for (i = 0; i < m + 2; i++)
{
MAZE[i][0] = 1;
MAZE[i][n + 1] = 1;
}
srand((int)time(NULL));//以系统当前时间设置随机数函数的种子。。
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
MAZE[i][j] = rand() % 2;//随机生成迷宫。。
MARK[i][j] = 0;//标志初始化为0。。
}
}
MAZE[1][1] = 0;//迷宫入口出口设置为可通过。。
MAZE[m][n] = 0;
MARK[1][1] = 1;
Q[1][0] = 1;//记录出发地点的坐标。。
Q[1][1] = 1;
Q[1][2] = 1;
for (i = 2; i < m * n; i++)
{
Q[i][2] = 0;
}
for (i = 1; i < m + 1; i++)
{
for (j = 1; j < n + 1; j++)
{
printf("%d", MAZE[i][j]);//输出迷宫。。
}
printf("\n");
}
i = 1;
int tempM;
int tempN;
while (Q[1][2] <= 8)
{
if ((Q[i][0] == m) && (Q[i][1]) == n)
{
if (i - 1 < minSteps)
{
minSteps = i - 1;
for (j = 1; j <= minSteps; j++)
{
Q[j][3] = Q[j][2];
}
}
MARK[m][n] = 0;
Q[i][2] = 0;
i--;
Q[i][2]++;
}
else
{
tempM = Q[i][0] + MOVE[Q[i][2]][1];//下一步的m。。
tempN = Q[i][1] + MOVE[Q[i][2]][2];//下一步的n。。
if ((MAZE[tempM][tempN] == 0) && (MARK[tempM][tempN] == 0))
{
i++;
MARK[tempM][tempN] = 1;
Q[i][0] = tempM;
Q[i][1] = tempN;
Q[i][2] = 1;
}
else
{
Q[i][2]++;
while ((Q[i][2] > 8) && (i != 1))
{
MARK[Q[i][0]][Q[i][1]] = 0;
Q[i][2] = 0;
i--;
Q[i][2]++;
}
}
}
}
if (minSteps == m * n)
{
printf("THERE IS NO PATH.");
} else
{
tempM = m;
tempN = n;
printf("(%d,%d)", m, n);
for (j = minSteps; j >= 1; j--)
{
tempM = tempM - MOVE[Q[j][3]][1];
tempN = tempN - MOVE[Q[j][3]][2];
printf("(%d,%d)", tempM, tempN);
}
}
printf("\n");
FreeTwoDimensionalArr(MAZE, m + 2, n + 2);//释放。。
FreeTwoDimensionalArr(MARK, m + 1, n + 1);
FreeTwoDimensionalArr(Q, m * n, 3);
}

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

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息