-迷宫问题实验报告(c编写-附源代码)汇总.doc

迷宫问题实验报告
级 班 年 月 日 姓名 学号_

1．实验题目
　　以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2．需求分析
本程序使用VC编写，实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路，或得出没有通路的结论。
① 输入的形式和输入值的范围：
A.输入指定的数字，以此选择迷宫的创建方式，分为手动创建迷宫和自动创建迷宫
B. 输入迷宫阵表的行数和列数，行数和列数不超过40行
C. 手动创建迷宫时，需要输入迷宫结点的通畅和障碍情况，0和1分别表示迷宫中的通路和障碍。
② 输出的形式：输出没有通路的结论，或者输出一个长方阵表，其中路径的每个结点都输出→、↓、←、↑之一，表示从当前结点到下一个结点的方向。
③ 程序所能达到的功能：实现设定迷宫或自动生成迷宫长方阵表的功能，并且求出一条从指定入口到指定出口的通路（迷宫的入口指定为坐标为（1,1）的结点，迷宫的出口指定为坐标为（迷宫最大行,迷宫最大列）的结点），或得出没有通路的结论。
④ 测试数据：
输入数据：
A． 出现选择生成迷宫方式的菜单时，输入1（即手动输入数据，生成迷宫）；
B． 输入迷宫的行数和列数，行数输入3，列数输入3；
C． 输入每个迷宫结点的信息：
0 0 1
1 0 0
1 0 0
输出结果：
→ ↓ 1
1 → ↓
1 0 0

3．概要设计
1) 为了实现上述程序功能，需要定义迷宫的抽象数据类型：
　typedef struct//定义迷宫结构体
{
int maze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息
int max_x,max_y; //迷宫的行数和和列数
}

2) 定义迷宫中点的指针的结构体
typedef struct point
{
int vex_x,vex_y; //结点的横纵坐标（横坐标为行号,纵坐标为列号）
struct point *ahead;//在链栈中，指向前一个结点的指针
int direction; //从当前结点走至下一个结点的方向
};

　基本操作：
　 A. Maze creat_manual()
初始条件：无
　　 操作结果：手动创建一个迷宫。
B. Maze creat_automatic()
初始条件：无
操作结果：自动创建一个迷宫。
　C. int found(int x,int y,Point *head)
初始条件：存在一个存放结点的链栈　　
操作结果：查找栈中是否有head指针内所含的坐标；若含，则返回1，否则返回0。
D. Point * find_road(Maze a)
初始条件：存在一个迷宫
操作结果：返回一条通路或者NULL
　 E. void display(Point *po,Maze a)
初始条件：存在一个迷宫
操作结果：输出结果。

程序包含6个函数：
　　主函数main()
　　手动创建一个迷宫 Maze creat_manual();
自动创建一个迷宫 Maze creat_automatic();
查找栈中是否有head指针内所含的坐标 int found(int x,int y,Point *head);
迷宫寻路函数 Point * find_road(Maze a);
显示迷宫信息函数 void display(Point *po,Maze a);

各函数间关系如下：

主函数
创建迷宫
迷宫求解函数
改变条件
输出路径
初始化
符和条件？
进栈
找到出口？

4．详细设计
1) 定义迷宫结构体
typedef struct
{
int maze_array[maxsize][maxsize];
//二维数组存放迷宫每个点是通畅或阻隔的信息
int max_x,max_y; //迷宫的行数和和列数
}Maze;
2) 定义迷宫中点的指针的结构体
typedef struct point
{
int vex_x,vex_y; //结点的横纵坐标（横坐标为行号,纵坐标为列号）
struct point *ahead;//在链栈中，指向前一个结点的指针
int direction; //从当前结点走至下一个结点的方向
}Point;

迷宫的基本操作如下
3) Maze creat_manual()//手动创建迷宫
{
输入迷宫的行数和列数；
依次输入各点的值；
}

4) Maze creat_automatic()//自动创建迷宫
{
输入迷宫的行数和列数；
随机产生各点的值；
入口结点和出口结点赋值为0；
打印迷宫；
}

5) int found(int x,int y,Point *head)

{
查找栈中是否有head指针内所含的坐标
若含，则返回1；
否则返回0
}

6) Point * find_road(Maze a)//迷宫寻路函数，返回一条通路或者NULL
{ int j,find,x,y;
do
{ while(方向j<4)
{ find=0；
switch(j)//1234分别表示东南西北
{ case 1:
if(纵坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现)
{
当前结点进栈；
把方向j赋予当前结点方向；
find=1;
}break;
case 2:
if(横坐标加1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现)
{ 当前结点进栈；
把方向j赋予当前结点方向；
find=1;
}break；

case 3:
if(纵坐标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现)
{
当前结点进栈；
把方向j赋予当前结点方向；
find=1;
}break；
case 4:
if(横标减1后在迷宫内，且当前结点为0，且当前结点没有在栈中出现)
{ 当前结点进栈；
把方向j赋予当前结点方向；
find=1;
}break;
}
if(find==1)
{ j++;break;}
else 方向加1，即换方向;
}
if(j>4)
{ if(栈顶前一个结点不为空)
{当前结点出栈且方向加1}
else return NULL;
}
}while(当前结点不是出口)
return top;

7) void display(Point *po,Maze a)//输出结果
{
int i,j,top=0;
Point *stack[maxsize];

if(指针==NULL)
cout<<"没有找到迷宫通路！"<<endl;
else
{
while(指针!=NULL)//通过一个栈将链栈逆序
{
stack[top++]=指针;
po指针指向前一个结点;
}

cout<<"迷宫通道如下："<<endl;
while(top>1)将栈中的通路所含结点的方向值加10
{
top--;
a.maze_array[当前新栈中所存的行坐标][当前新栈中所存的列坐标]=新栈中当前结点到下一个结点的方向+10;
//11、12、13、14分别为东、南、西、北
}

for(i=1;i<=行最大值;i++)//打印迷宫
{
for(j=1;j<=列最大值;j++)
{
if(结点值<=1)
cout<<结点值<<" ";
else//根据结点内所存储的方向值，对应输出四个方向的箭头之一，指示从该结点到下一个结点的方向
{
switch(结点值)
{
case 东:输出->； break;
case 南: 输出↓；break;
case 西: 输出<- ；break;
case 北: 输出↑；break; }}}}}
5．调试分析
通过本试验我对链栈有了更深入的了解。在编写程序的过程中，我们更容易发现问题所在，对算法有更深会的理解。
判断方向的转变使其不会重复走过的路经，这个比较麻烦，当时也不知道如何不让迷宫走“回头路”，只能是查资料，和同学讨论，最终找到了解决办法。
6．使用说明
程序名为：迷宫.exe，运行环境为DOS。程序执行后显示　
请选择手动或自动生成迷宫
1.手动生成迷宫
2.自动生成迷宫

输入数字选择执行不同的功能。
输入1，使用手动生成迷宫功能；
输入2，使用自动生成迷宫功能；
输入其他数字，则提示输入错误，需要重新输入数字选择功能，直至输入的数字为1或2为止。
输入其他数字后，输出的画面如下：
您输入的数值有误，请重新输入
请选择手动或自动生成迷宫
1.手动生成迷宫
2.自动生成迷宫
输入1后，接着输入迷宫的行数和列数，最后出现如下画面

此时请依次输入每个结点的值，其中入口和出口必须输入0：
接着程序会输出迷宫通路或者是没有通路的信息
使用自动创建迷宫功能时，只需输入行数和列数，接着程序会输出迷宫通路或者是没有通路的信息

7．测试结果
1) 5X5迷宫，没路的情况，输入和输出如下所示：

2) 5X5迷宫，有通路情况，输入和输出如下所示：

3) 4X3迷宫，没路情况，输入和输出如下所示：

4) 4X3迷宫，有路情况，输入和输出如下所示：

源代码如下：
# include <iostream>
using namespace std;
#include<time.h>
#include<stdlib.h>
# define maxsize 20

typedef struct//定义迷宫结构体
{
int maze_array[maxsize][maxsize];//二维数组存放迷宫每个点是通畅或阻隔的信息
int max_x,max_y; //迷宫的行数和和列数
}Maze;

typedef struct point//定义迷宫中点的指针的结构体
{
int vex_x,vex_y; //结点的横纵坐标（横坐标为行号,纵坐标为列号）
struct point *ahead;//在链栈中，指向前一个结点的指针
int direction; //从当前结点走至下一个结点的方向
}Point;

Maze creat_manual()//手动创建迷宫
{
int i,j;
Maze temp;

cout<<"请输入迷宫的行数: ";
cin>>temp.max_x;
cout<<"请输入迷宫的列数: ";
cin>>temp.max_y;

cout<<"迷宫的入口和出口已经指定；"<<endl;
cout<<"迷宫的入口结点坐标为（1,1），输入该结点的值时，请输入0。"<<endl;
cout<<"迷宫的出口结点坐标为"<<"（"<<temp.max_x<<","<<temp.max_y<<"）"<<"，输入该结点的值时，请输入0。"<<endl;

cout<<"结点值为0表示通畅，值为1表示阻隔"<<endl<<endl;
for(i=1;i<=temp.max_x;i++)
{
cout<<"请输入迷宫第"<<i<<"行各点的值：";
for(j=1;j<=temp.max_y;j++)
cin>>temp.maze_array[i][j];
}

cout<<endl;
return temp;
}

Maze creat_automatic()//自动创建迷宫
{
int i,j;
Maze temp;

cout<<"请输入迷宫的行数: ";
cin>>temp.max_x;
cout<<"请输入迷宫的列数: ";
cin>>temp.max_y;

unsigned int t;
t=time(NULL)%1000;
srand(t);//产生随机数种子

for(i=1;i<=temp.max_x;i++)
{
for(j=1;j<=temp.max_y;j++)
{
temp.maze_array[i][j]=rand()%2;
}
}

temp.maze_array[1][1]=0;//迷宫入口置值为0
temp.maze_array[temp.max_x][temp.max_x]=0;//迷宫出口置值为0，否则程序不能正常运行

for(i=1;i<=temp.max_x;i++)//打印迷宫
{
for(j=1;j<=temp.max_y;j++)
{
cout<<temp.maze_array[i][j]<<" ";
}
cout<<endl;
}

cout<<endl;
return temp;
}

int found(int x,int y,Point *head)//查找栈中是否有head指针内所含的坐标；若含，则返回1，否则返回0
{
Point *p=head;

while(p!=NULL)
{
if(x==p->vex_x&&y==p->vex_y)
return 1;
p=p->ahead;
}
return 0;
}

Point * find_road(Maze a)//迷宫寻路函数，返回一条通路或者NULL
{
Point *top,*p;//top为栈的栈顶指针
int j,find,x,y;

p=(Point *)malloc(sizeof(Point));
p->ahead=NULL;
p->vex_x=1;p->vex_y=1;
top=p;
j=1;//j为方向，1、2、3、4分别为东、南、西、北

do
{
while(j<=4)
{
find=0;//find判断是否为符合条件的结点，若有为1，没有为0
x=p->vex_x;
y=p->vex_y;
switch(j)
{
case 1:
if(y+1<=a.max_x&&!a.maze_array[x][y+1]&&!found(x,y+1,top))
//若纵坐标加1后，在迷宫范围内；且该结点为0；且该结点没有在链栈中出现，则当前结点加入链栈
{
p=(Point *)malloc(sizeof(Point));
p->vex_x=x; p->vex_y=y+1;
p->ahead=top;
top->direction=j;//从上一结点至该结点的方向，存放在上一结点的结点指针内
top=p;
find=1;
}break;

case 2:
if(x+1<=a.max_x&&!a.maze_array[x+1][y]&&!found(x+1,y,top))
{
p=(Point *)malloc(sizeof(Point));
p->vex_x=x+1; p->vex_y=y;
p->ahead=top;
top->direction=j;
top=p;
find=1;
}break;

case 3:
if(y-1>=1&&!a.maze_array[x][y-1]&&!found(x,y-1,top))
{
p=(Point *)malloc(sizeof(Point));
p->vex_x=x; p->vex_y=y-1;
p->ahead=top;
top->direction=j;
top=p;
find=1;
}break;

case 4:
if(x-1<=1&&!a.maze_array[x-1][y]&&!found(x-1,y,top))
{
p=(Point *)malloc(sizeof(Point));
p->vex_x=x-1;p->vex_y=y;p->ahead=top;
top->direction=j;
top=p;
find=1;
}break;
}

if(find==1)//若找到符合条件的结点，则j赋值为1，然后退出内层while循环
{
j=1;
break;
}
else
j++; //若没有，j加1
}

if(j>4)//4个方向都找不到符合条件的结点时
{
if(top->ahead!=NULL)//若top不为空，则出栈，上一个结点的方向j加1
{
p=p->ahead;
top=p;//使栈顶结点指向前一个节点，原节点删除
j=top->direction+1;
top->direction=j;
}
else
return NULL;//若top为空，则返回NULL
}

}while(top->vex_x!=a.max_x || top->vex_y!=a.max_y);//若果当前结点不是出口，则继续进行do-while循环
return top;
}

void display(Point *po,Maze a)//输出结果
{
int i,j,top=0;
Point *stack[maxsize];

if(po==NULL)
cout<<"没有找到迷宫通路！"<<endl;
else
{
while(po!=NULL)//通过一个栈将链栈逆序
{
stack[top++]=po;
po=po->ahead;
}

cout<<"迷宫通道如下："<<endl;
while(top>1)//出口结点值为0，无方向，不需要把方向赋值给该结点
{
top--;
a.maze_array[stack[top]->vex_x][stack[top]->vex_y]=stack[top]->direction+10;
//把迷宫通路走的方向赋值给迷宫中相应的结点
//11、12、13、14分别为东、南、西、北
}

for(i=1;i<=a.max_x;i++)//打印迷宫
{
for(j=1;j<=a.max_y;j++)
{
if(a.maze_array[i][j]<=1)
cout<<a.maze_array[i][j]<<" ";
else//根据结点内所存储的方向值，对应输出四个方向的箭头之一，指示从该结点到下一个结点的方向
{
switch(a.maze_array[i][j])
{
case 11:
printf("%c ",26);//输出->
break;
case 12:
printf("%c ",25);//输出向下的箭头
break;
case 13:
printf("%c ",27);//输出<-
break;
case 14:
printf("%c ",24);//输出向上的箭头
break;
}
}
}
cout<<endl;
}

cout<<endl;
}
}

void main()
{
Maze a;
Point *po;
int selection;

cout<<"请选择手动或自动生成迷宫"<<endl;
cout<<"1.手动生成迷宫"<<endl;
cout<<"2.自动生成迷宫"<<endl;
cin>>selection;

while(selection!=1&&selection!=2)
{
cout<<"您输入的数值有误，请重新输入"<<endl;
cout<<"请选择手动或自动生成迷宫"<<endl;
cout<<"1.手动生成迷宫"<<endl;
cout<<"2.自动生成迷宫"<<endl;
cin>>selection;
}

if(selection==1)
a=creat_manual();
else
a=creat_automatic();

po=find_road(a);
display(po,a);
getchar();
getchar();
}
第 19页，共19页