实验报告：迷宫问题

题目：编写一个求解迷宫通路的程序

一、        需求分析：

1)         采用二维数组maze[M][N]来表示迷宫，其中：maze[0][j]和maze[M-1][j](0≤j≤N-1)及maze[i][0]和maze[i][N-1](0≤i≤M-1)为添加在迷宫外围的一圈障碍。数据元素值0表示通路，1表示障碍。限定迷宫的大小M≤8，N≤10.

2)         本次实验直接在主程序中输入表示迷宫的二维数组。另外，迷宫的入口和出口位置都将在主程序中直接设置。

3)         实验中求出的迷宫通路用“-”表示，迷宫的障碍用“#”表示，已走过但未能求出通路的路径用“@”表示。

4)         本程序只求出一条成功的通路。

5)         本次实验将直接输出构建迷宫的二维数组、初始化的二维数组和求解后的迷宫数组。

二、        概要设计：

数据结构及其抽象数据类型的定义。

（1）栈的抽象数据类型

ADT Stack{

数据对象：D={ai| ai∈CharSet,i=1,2…n,n＞=0}

数据关系：R1={| ai-1, ai∈D,i=2,…n}

基本操作：

InitStack(&S)

操作结果：构造一个空栈S。

DestroyStack(&S)

初始条件：栈S已存在。

操作结果：销毁栈S。

ClearStack(&S)

初始条件：栈S已存在。

操作结果：将S清为空栈。

StackLength(S)

初始条件：栈S已存在。

操作结果：返回栈S的长度。

StackEmpty(S)

初始条件：栈S已存在。

操作结果：若S为空栈，则返回TRUE，否则返回FALSE。

GetTop(S，&e)

初始条件：栈S已存在。

操作结果：若栈S不空，则以e返回栈顶元素。

Push(&S， e)

初始条件：栈S已存在。

操作结果：在栈S的栈顶插入新的栈顶元素e。

Pop(&S，&e)

初始条件：栈S已存在。

操作结果：删除S的栈顶元素，并以e返回其值。

StackTraverse（S，visit（））

初始条件：栈S已存在。

操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。

} ADT Stack

（2）迷宫的抽象数据类型

ADT maze{

数据对象：D={ai,j| ai,j∈{ ' ','#','@','*'},0＜=i＜=m+1,0＜=j＜=n+1,m,n＜=10}

数据关系：R={ROW,COL}

基本操作：

InitMaze(&M,a,row,col)

初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。

操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符‘#’表示障碍，并在迷宫四周加上一圈障碍。

MazePath(&M)

初始条件：迷宫M已被赋值。

操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符’*’表示路径上的位置，字符‘@’表示“死胡同”，否则迷宫的状态不变。

PrintMaze（M）

初始条件：迷宫M已存在。

操作结果：以字符形式输出迷宫。

} ADT maze

三、        详细设计：

1、 程序具体代码为：

// MazePath.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#define  TRUE 1

#define  FALSE   0

#define  OK  1

#define  ERROR   0

#define INFEASIBLE   -1

#define OVERFLOW   -2

#include

#include

#include

#include

typedef  int  Status;

#define  RANGE   20     //RANGE为实际分配的空间行列数

#define M 8             //maze数组的行数

#define N 11            // maze数组的列数

typedef struct          //表达迷宫元素位置信息的坐标

{

    int r,c;

}PosType;

typedef struct//m，n为待处理的迷宫的行列数，RANGE为实际分配的空间行列数

{

    int m,n;

    char arr[RANGE][RANGE];

}MazeType;

typedef int directiveType;//东西南北方向用1，2，3，4整数对应

typedef struct//路径拟用栈来存储，此处定义栈元素中数据域的信息

{

    int step;//存储到达该点时经历的步数

    PosType seat;//该点位置

    directiveType di;//从该点位置走向下一位置的方向

}ElemType;

typedef struct NodeType//路径拟用链栈来存储

{

    ElemType data;

    struct NodeType *next;

}NodeType,*LinkType;

typedef struct//对链栈的头指针和元素个数进行封装

{

    LinkType top;

    int size;

}Stack;

//以上是对存储结构逐层进行定义

void   InitStack(Stack  &S)  

{   //构建空链栈，不带头结点

    S.top=NULL;  

    S.size=0;  

}  

Status   MakeNode(LinkType &p,ElemType   e)  

{   //创建一个新结点，以便插入，本函数可作为链式存储创建结点的通用函数，可用于链表、链栈、链队的插入操作

    p=(NodeType *)malloc(sizeof(NodeType));  

    if(!p)

        return   FALSE;  

    p-＞data=e;

    p-＞next=NULL;  

    return   TRUE;  

}

Status   Push(Stack   &S,ElemType   e)  

{   //入栈操作，在这里本质上是栈头（链表头）进行插入

    LinkType   p;  

    if(MakeNode(p,e))  

    {  

        p-＞next=S.top;  

        S.top=p;  

        S.size++;  

        return   TRUE;  

    }  

    return   FALSE;  

}

Status   StackEmpty(Stack   S)  

{   //判断是否为空栈，这里是通过top指针为NULL来判断的，本质上也可以通过size是否为0来判断

    if(S.top==NULL)

        return   TRUE;

    return  FALSE;  

} 

Status   Pop(Stack   &S,ElemType   &e)

{   //出栈操作，本质上是删除表头元素

    LinkType   p;

    if(StackEmpty(S))

        return   FALSE;

    else

    {

        p=S.top;

        S.top=S.top-＞next;

        e=p-＞data;

        S.size--;

        free(p);

        return   TRUE;

    }         

}  

Status   pass(MazeType  maze,PosType  curpos)  

{   //判断迷宫Maze中，当前位置curpos是否是一个可达位置

    int   m,n;   //注意这里的m，n只是表达下标的临时变量，与前面出现的m，n是不一样的

    m=curpos.r;  

    n=curpos.c;  

    if(maze.arr[m][n]==' ')

        return   TRUE;  

    return   FALSE;  

}

Status   Same(PosType  curpos,PosType  end)  

{   //判断当前位置curpos是否已达出口

    if(curpos.r==end.r && curpos.c==end.c)

        return   TRUE;  

    return   FALSE;  

}

void   FootPrint(MazeType &maze,PosType curpos)  

{   //在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环

    int   m,n;  

    m=curpos.r;  

    n=curpos.c;  

    maze.arr[m][n]='-';  

}

PosType   NextPos(PosType curpos,int di)  

{   //通过di的值，确定下一步的位置，下一步位置实际是当前位置的四个邻居中的一个

    switch(di)

    {

    case 1:

        curpos.c++; //向东走

        break;     

    case 2:

        curpos.r++; //向南走

        break;

    case 3:

        curpos.c--; //向西走

        break;     

    case 4:

        curpos.r--;  //向北走

        break;

    }  

    return   curpos;   

}

void  MarkPrint(MazeType &maze,PosType p)  

{   //对试探无路可走后回退的位置做特殊标识

    maze.arr[p.r][p.c]='@';  

}

void  PrintMaze(MazeType ma)  

{   //对迷宫输出，实际是对一个二维数组的输出

    int i,j;

    printf("\n");

    for(i=0;i

    {  

        printf("\t");

        for(j=0;j

        {  

            printf("%c ",ma.arr[i][j]);  

        }  

        printf("\n");  

    }

    printf("\n");

}

void   InitMaze(MazeType  &maze,int  a[][N],int row,int col)  

{   //根据二维数组来初始化迷宫，这个二维数组可以设计为由用户从键盘输入，解决不同迷宫的问题，但这里用户接口不是我们考虑的重点

    //数据结构学习时往往将输入的数据直接嵌入到程序中，以简化输入节约时间

    //二维数组名a做参数时，需要知道待读的二维数组的列数，因为C语言中二维数组是按行优先顺序存储的

    //控制每行长度的实际就是定义列的数值，所以要明确参数N

    int i,j;

    maze.m=row;

    maze.n=col;

    for(i=0;i

        for(j=0;j

        {  

            if(a[i][j]==0)

                maze.arr[i][j]=' ';

            else

                maze.arr[i][j]='#';  

        }  

}

/*

int   MazePath(MazeType &maze,PosType start,PosType end)  

{   //求解迷宫的关键函数，maze作为引用型变量是因为要对相关路径做一些标识

//返回值为路径的长度,返回0表示无通路

Stack   s;  

int   curstep=1;   //统计路径长度实际可不用curstep，栈s中的size分量已有相关信息，修改一下程序curstep可以用于统计走过的总步数

int   found=0;  

ElemType   e;   //以栈元素的形式暂存当前位置的相关信息，以便入栈构成路径

PosType   curpos=start; //置开始位置为当前位置

InitStack(s);

do{   //栈不空且未到出口则继续循环

if(pass(maze,curpos))   //如果curpos位置可达则先入栈

{  

FootPrint(maze,curpos);   //如果可通则标记为-，当然后边如发现是死胡同，则会重新标记为另外的符号

e.step=curstep;  

e.seat=curpos;  

e.di=1;           

Push(s,e);  

if(Same(curpos,end))

{

found=s.size;

}

else

{  

curpos=NextPos(curpos,1);  //到新位置时默认先向东走

curstep++;  

}  

}  

else if(!StackEmpty(s))  

{  

Pop(s,e);   //如果curpos位置不可达，且栈不空，则把刚入栈的元素弹出做相关判断

while((e.di==4) && !StackEmpty(s))

{  

MarkPrint(maze,e.seat); //标识此路不通 

Pop(s,e);   //回到上一个位置

curstep--;   //不减一的话可以用于统计走过的总步数

}  

if(e.di＜4)//如果还有方向未走过，则沿新的方向继续试探

{  

e.di++;  

Push(s,e);  //默认新方向的下一位置可达，将当前位置入栈

curpos=NextPos(e.seat,e.di);  //通过当前位置，以及去下一位置的方向得出新的位置，再循环查看新位置是否可达

}

}      

}while(!StackEmpty(s) && !found);  

return   found;  

} 

*/

int  MazePath(MazeType &maze,PosType start,PosType end)

{//此函数为递归方法求迷宫的算法

    static int steps=1;

    if(Same(start,end))

    {

        FootPrint(maze,start);

        return steps;

    }

    else if(pass(maze,start))

    {

        FootPrint(maze,start);

        if(MazePath(maze,NextPos(start,1),end)+

            MazePath(maze,NextPos(start,2),end)+

            MazePath(maze,NextPos(start,3),end)+

            MazePath(maze,NextPos(start,4),end)＞0)//判断下一位置是否可走

        {

            return steps++;//返回抵达出口时的步数

        }

        else

        {

            MarkPrint(maze,start);//输出迷宫以及路径

            return FALSE;

        }

    }

    else

    {

        return FALSE;

    }

}

void Print(int maze[][N])

{

    int i,j;

    printf("表示迷宫的数组\n");

    for(i=0;i

    {

        printf("\t");

        for(j=0;j

        {

            printf("%d ",maze[i][j]);

        }

        printf("\n");

    }

    printf("\n");

}

void main()

{

    int step=0;

    int maze[M][N]={

        1,1,1,1,1,1,1,1,1,1,1,

        1,0,1,0,0,1,1,1,0,0,1,

        1,0,0,0,0,0,1,0,0,1,1,

        1,0,1,1,1,0,0,0,1,1,1,

        1,0,0,0,1,0,1,1,0,1,1,

        1,1,0,0,1,0,1,1,0,0,1,

        1,1,1,0,0,0,0,0,0,0,1,

        1,1,1,1,1,1,1,1,1,1,1};//在程序中直接输入一个建立迷宫的数组

        MazeType L;

        PosType   start,end;

        Print(maze);//调用Print函数输出直接输出已建立的迷宫数组

        InitMaze(L,maze,M,N);//调用InitMaze函数将二维数组初始化为迷宫

        start.r=1;

        start.c=1;//设置迷宫的入口

        end.r=6;

        end.c=9;//设置迷宫的出口

        printf("由数组转化出的迷宫");

        PrintMaze(L);//输出已转化的迷宫

        if(step=MazePath(L,start,end))

            printf("迷宫的路径，用-表示,路径长度为:%d",step);

        else

            printf("此迷宫没有通路！");

        PrintMaze(L);

}

2、 程序调用关系为：

四、        调试分析：

1)         本次实验采用两种求解迷宫路径的核心算法，一种是直接调用相关问题的函数，另一种是采用递归函数的方法（实验详细设计中采用的是第二种）。相比较第一种方法，采用递归的方法更加简洁明了。另外，本次实验为了方便起见采用了直接在主程序中输入用于构建迷宫的二维数组的方法，其实可以采用文件形式来输入构建迷宫的二维数组。

2)         本次实验中的另一个的核心就是如何建立存储迷宫的数据结构，即如何用链栈来存储迷宫路径中的各位置以及下一步将要走的方向。

3)         对试探无路可走后回退的位置要做特殊标识，另外还要在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环。

4)         本题中主要算法：PrintMaze和MazePath的时间复杂度均为O（m*n），故本次实验的空间复杂度也为O(m*n).

五、        用户手册：

1.         本次实验程序的运行环境为DOS操作系统，执行文件为：migong.exe.

2.         进入实验程序的演示后，用户界面将直接显示在主程序中输入的数组

3.         初始化数组成为迷宫：

六、        测试结果：

二组测试数据以及输出结果分别如下：

1)         主程序中输入的迷宫数据为：

入口位置：1   1

出口位置：6   9

求解路径后输出的迷宫为:

2)         主程序输入的迷宫数据为：

入口位置：1  1

出口位置：1  9

求解路径后输出的迷宫为：

附录：

源程序文件名清单：

base.H   //公用的常量和类型

stkpas.H  //栈类型

maze.H   //迷宫类型

testmaze.C   //主程序