迷宫问题实验报告（c 编写，附源代码）汇总

迷宫问题实验报告

级 班 年 月 日 姓名 学号_

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; //迷宫的行数和和列数

第 1页，共19页

}

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个函数：

1主函数main() ○

2手动创建一个迷宫 Maze creat_manual(); ○

3自动创建一个迷宫 Maze creat_automatic(); ○

4查找栈中是否有head指针内所含的坐标 int found(int x,int y,Point *head); ○

5迷宫寻路函数 Point * find_road(Maze a); ○

6显示迷宫信息函数 void display(Point *po,Maze a); ○

各函数间关系如下：

第 2页，共19页

主函数

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

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()//手动创建迷宫

{

输入迷宫的行数和列数；

第 3页，共19页

依次输入各点的值； }

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赋予当前结点方向；

第 4页，共19页

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;

第 5页，共19页

7) void display(Point *po,Maze a)//输出结果

{

int i,j,top=0;

Point *stack[maxsize];

if(指针==NULL)

cout<<\没有找到迷宫通路！\else {

while(指针!=NULL)//通过一个栈将链栈逆序 {

stack[top++]=指针; po指针指向前一个结点; }

cout<<\迷宫通道如下：\

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; }}}}}

第 6页，共19页

5．调试分析

通过本试验我对链栈有了更深入的了解。在编写程序的过程中，我们更容易发现问题所在，对算法有更深会的理解。

判断方向的转变使其不会重复走过的路经，这个比较麻烦，当时也不知道如何不让迷宫走“回头路”，只能是查资料，和同学讨论，最终找到了解决办法。 6．使用说明

程序名为：迷宫.exe，运行环境为DOS。程序执行后显示 请选择手动或自动生成迷宫 1.手动生成迷宫 2.自动生成迷宫

输入数字选择执行不同的功能。 输入1，使用手动生成迷宫功能； 输入2，使用自动生成迷宫功能；

输入其他数字，则提示输入错误，需要重新输入数字选择功能，直至输入的数字为1或2为止。

输入其他数字后，输出的画面如下： 您输入的数值有误，请重新输入 请选择手动或自动生成迷宫 1.手动生成迷宫 2.自动生成迷宫

输入1后，接着输入迷宫的行数和列数，最后出现如下画面

此时请依次输入每个结点的值，其中入口和出口必须输入0： 接着程序会输出迷宫通路或者是没有通路的信息

使用自动创建迷宫功能时，只需输入行数和列数，接着程序会输出迷宫通路或者是没有通路的信息

第 7页，共19页

7．测试结果

1) 5X5迷宫，没路的情况，输入和输出如下所示：

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

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

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

第 8页，共19页

源代码如下：

# include using namespace std; #include #include # 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<<\请输入迷宫的行数: \

第 9页，共19页

cin>>temp.max_x;

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

cout<<\迷宫的入口和出口已经指定；\

cout<<\迷宫的入口结点坐标为（1,1），输入该结点的值时，请输入0。\

cout<<\迷宫的出口结点坐标为\（\）\，输入该结点的值时，请输入0。\ }

Maze creat_automatic()//自动创建迷宫 {

int i,j; Maze temp;

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

第 10页，共19页

cout<<\结点值为0表示通畅，值为1表示阻隔\for(i=1;i<=temp.max_x;i++) { }

cout<<\请输入迷宫第\行各点的值：\for(j=1;j<=temp.max_y;j++)

cin>>temp.maze_array[i][j];

cout<

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

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

for(i=1;i<=temp.max_x;i++) { }

temp.maze_array[1][1]=0;//迷宫入口置值为0

for(j=1;j<=temp.max_y;j++) { }

temp.maze_array[i][j]=rand()%2;

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

第 11页，共19页

for(i=1;i<=temp.max_x;i++)//打印迷宫 { }

for(j=1;j<=temp.max_y;j++) { }

cout<

cout<

}

cout<

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

Point * find_road(Maze a)//迷宫寻路函数，返回一条通路或者NULL {

p=(Point *)malloc(sizeof(Point)); p->ahead=NULL; p->vex_x=1;p->vex_y=1; top=p;

第 12页，共19页

Point *p=head;

while(p!=NULL) { } return 0;

if(x==p->vex_x&&y==p->vex_y)

return 1;

p=p->ahead;

Point *top,*p;//top为栈的栈顶指针 int j,find,x,y;

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))

第 13页，共19页

{

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;

第 14页，共19页

find=1;

}break;

}

}

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

j++; //若没有，j加1 j=1; break;

if(j>4)//4个方向都找不到符合条件的结点时

{

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

第 15页，共19页

}

if(top->ahead!=NULL)//若top不为空，则出栈，上一个结点的方向j加1 { } else

return NULL;//若top为空，则返回NULL p=p->ahead;

top=p;//使栈顶结点指向前一个节点，原节点删除 j=top->direction+1; top->direction=j;

}

return top;

void display(Point *po,Maze a)//输出结果 {

int i,j,top=0; Point *stack[maxsize];

if(po==NULL)

cout<<\没有找到迷宫通路！\

else {

while(po!=NULL)//通过一个栈将链栈逆序 { }

cout<<\迷宫通道如下：\

while(top>1)//出口结点值为0，无方向，不需要把方向赋值给该结点 {

top--;

stack[top++]=po; po=po->ahead;

a.maze_array[stack[top]->vex_x][stack[top]->vex_y]=stack[top]->direction+10;

//把迷宫通路走的方向赋值给迷宫中相应的结点 //11、12、13、14分别为东、南、西、北

}

第 16页，共19页

for(i=1;i<=a.max_x;i++)//打印迷宫

{

for(j=1;j<=a.max_y;j++) {

if(a.maze_array[i][j]<=1)

cout<

else//根据结点内所存储的方向值，对应输出四个方向的箭头之一，指示从该结点到下一个结点的方向

}

{ }

switch(a.maze_array[i][j]) {

case 11: }

printf(\输出-> break;

case 12:

printf(\输出向下的箭头 break;

case 13:

printf(\输出<- break;

case 14:

printf(\输出向上的箭头 break;

cout<

第 17页，共19页

}

}

cout<

void main() {

第 18页，共19页

Maze a; Point *po; int selection;

cout<<\请选择手动或自动生成迷宫\cout<<\手动生成迷宫\cout<<\自动生成迷宫\cin>>selection;

while(selection!=1&&selection!=2) {

cout<<\您输入的数值有误，请重新输入\cout<<\请选择手动或自动生成迷宫\

cout<<\手动生成迷宫\ cout<<\自动生成迷宫\ cin>>selection; }

if(selection==1)

a=creat_manual();

else a=creat_automatic();

po=find_road(a); display(po,a); getchar(); getchar();

}

第 19页，共19页

本文来源：https://www.bwwdw.com/article/6jwt.html