[数据结构]深度与广度优先搜索：迷宫问题

1、数据结构课程设计深度与广度优先搜索:迷宫问题数据结构课程设计深度与广度优先搜索：迷宫问题专业Xxxxx学生姓名xxxxxx班级xxxxxxxxx 学号xxxxxxxxxxxxxxxx1目录1 设计题目12 设计分析13 设计实现34测试方法34.1测试目的84.2 测试输入84.3 正确输出94.4 实际输出94.5 错误原因115 分析与探讨115.1 测试结果分析115.2 探讨与改进116 设计小结11 7 参考文献 11 设计题目 a)迷宫问题求解的目标：寻找一条从入口点到出口点的通路。(迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。)例如，可以设计一个8*8矩阵m

2、aze88来表示迷宫，如下所示：0 1 0 0 0 0 1 10 0 0 1 0 0 1 01 0 1 0 1 0 1 11 0 1 0 1 1 0 10 1 1 1 1 1 1 01 0 0 1 1 0 0 01 0 1 0 0 0 1 11 0 1 1 0 1 0 0左下角maze00为起点，右下角maze77为终点；设“0”为通路，“1”为墙，既无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。b)设计程序要求：能自动生成或者手动生成这样一个8*8矩阵；针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。如果不能，请指出；如果

3、能，请用图形界面标出走出迷宫的路径。2 设计分析a)首先明确题目中的已知条件：·迷宫是一个8*8大小的矩阵。·从迷宫的左上角进入，右下角为迷宫的终点。·mazeij=0代表第i+1行第j+1列的点是通路；mazeij=1代表该点是墙，无法通行。·迷宫有两种生成方式：手工设定和自动生成。·当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8个方向。·要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组,mazeN+2N+2来表示这个迷宫，其中N为迷宫的行、列数。当值为

4、“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以用行号row和列号col表示。b)为什么指定mazeN+2N+2表示迷宫，而不是使用mazeNN来表示迷宫？·原因是当老鼠跑到迷宫的边界点时就有可能跳出迷宫；而使用mazeN+2N+2就可以把迷宫的外面再包一层“1”，这样就能阻止老鼠走出格。c)老鼠再每一点都有8种方向可以走，分别是：North，NorthEast,East,SouthEast,East,South,SouthWest,West,NorthWest.可以用数组move8来表示在每一个方向上的横纵坐标的偏移量，见表21。根据这个数组，

5、就很容易计算出沿某个方向行走后的下一点的坐标。Namedir Movedir.vert Movedir.horiz N0-1 0 NE1-1 1 E20 1 SE31 1 S41 0 SW51 -1 W60 -1 NW60 -1 表21 8种方向move的偏移量d)迷宫问题可以用深度优先搜索方法实现。当老鼠当老鼠在迷宫中移动的时候，可能会有多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选取一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当前各方向上都走不通时可以返回上一个点，然后选择另一个方向前进。·可定义element结构用于存储每一步的横纵坐标和方向

6、。 typedef struct short int row; short int col; short int dir; element;Element stackMAX _STACK_SIZE;根据表21可推算出每次移动后的坐标。设当前的坐标是(row,col),移动的方向是dir，移动后的点是next,则有next_row=row+movedir.vert;next_col=col+movedir.horiz;·可用另一个二维数组markN+2来记录哪些点已经被访问过。当经过点mazerowcol时，相应地将markrowcol的值从0置为1。e)本程序支持自动生成迷宫。利用r

7、andom(2)函数可随机产生0或1，来支持迷宫的自动生成。注意mazeNN和maze11一定要等于0，因为他们分别是起点和终点。f)如果找到了一条走出迷宫的路径，则需要在屏幕中打印出走出迷宫的信息。这里要用到graphics.h。为画出效果图，可使用circle()函数画圆，outtexttxy()函数标记文字，并用line()函数来划线。g)程序的主要函数如下：·函数void add(int*top,element item)，将当前步的信息item压入到作为全局变量的栈stack(栈顶为top)中。·函数element delete(int * top)，返回stac

8、k中栈顶的元素。·函数void path(void)，采用深度优先搜索算法，首先取出栈顶元素作为当前点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个点压入栈，并将二维数组mark中对应的值改为1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了（已经尝试了各个方向并失败），并且这个点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点；当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。3 设计实现/*This program can be compiled under VC6.0*/#inclu

9、de <stdio.h>#include <stdlib.h>#include <graphics.h>#include<time.h>#include<conio.h>#define N 8#define MAX_STACK_SIZE N*N/*最大栈容量 */#define TRUE 1#define FALSE 0#define LEN (300/N)/*结构体记录每一步的横坐标，纵坐标和方向*/typedef struct short int row;short int col;short int dir;element;el

10、ement stackMAX_STACK_SIZE;/*结构体记录水平和垂直的偏移量*/typedef struct short int vert;short int horiz;offsets;offsets move8; /* 8个方向的move*/int mazeN+2N+2;/*二维数组记录迷宫*/int markN+2N+2;/*记录迷宫中每点是否可到达*/int EXIT_ROW = N, EXIT_COL = N;/*在栈中加入一个元素*/void add(int *top, element item)if (*top >= MAX_STACK_SIZE - 1)print

11、f("The stack is full!n");return; stack+*top = item;/*返回栈中顶部的元素*/element delete_top(int *top)if (*top = -1)printf("The stack is empty ! n");exit(1); return stack(*top)-;/*输出走出迷宫的路径*/void path(void) int i, j, k, row, col, next_row, next_col, dir, found = FALSE; int gd=VGA; int gm=V

12、GAHI;/*-*|i ->用来循环计数 |row , col ->当前位置的坐标 |next_row ->移动后的位置的横坐标 |next_col ->移动后的位置的纵坐标|dir ->移动的方向 |found ->标志路径是否发现 |*-*/ element position; int top = 0; mark11 = 1; /* maze11已经被走过了*/ stack0.row = 1; stack0.col = 1; stack0.dir = 1; /*第一步的状态*/ move0.vert = -1; move0.horiz = 0 ; mov

13、e1.vert = -1; move1.horiz = 1 ; move2.vert = 0 ; move2.horiz = 1 ; move3.vert = 1 ; move3.horiz = 1 ; move4.vert = 1 ; move4.horiz = 0 ; move5.vert = 1 ; move5.horiz = -1; move6.vert = 0 ; move6.horiz = -1; move7.vert = -1; move7.horiz = -1; initgraph(&gd,&gm,""); /* 指定了八个方向*/ /*-*

14、 | 主要算法描述: | | 当stack不为空,移动到stack顶部的位置 | | 试着向各个方向移动，如果可以移动就移动到 | 下一个位置并把它标志成1。 | | 然后保存状态并加入到stack中 | | 如果路径被破坏，或者不存在，就将其删除 | | 并返回到上一点继续遍历其他方向的点 | | 直到一条路径被发现。 | *-*/ while ( top > -1 && !found) /*stack不为空*/ position = delete_top(&top); /*删除stack中的元素*/ row = position.row; col = posi

15、tion.col; dir = position.dir; while (dir < 8 && !found) next_row = row + movedir.vert; next_col = col + movedir.horiz; if (next_row = EXIT_ROW && next_col = EXIT_COL) found = TRUE; /*发现路径*/ else if ( !mazenext_rownext_col && !marknext_rownext_col) /*如果这点没有被走过并且可以走*/ markne

16、xt_rownext_col = 1; /*设成1*/ position.row = row; position.col = col; position.dir = +dir; add(&top, position); /*加入到stack*/ row = next_row; col = next_col; dir = 0; /* 移动到下一个点 */ else +dir; /*尝试其他方向*/ for(j=1;j<=N;j+) for(k=1;k<=N;k+) setcolor(WHITE); circle(j*LEN,k*LEN,10); setcolor(MAGENT

17、A); outtextxy(j*LEN-2,k*LEN-2,mazekj?"1":"0"); if (found) /* 如果发现路径，则打印出来*/ outtextxy(20,10,"The path is:"); setcolor(YELLOW); for (i=0; i <top;i+) line(stacki.col*LEN, stacki.row*LEN,stacki+1.col*LEN,stacki+1.row*LEN); line(stacki.col*LEN, stacki.row*LEN,col*LEN,row

18、*LEN); line(col*LEN, row*LEN,EXIT_COL*LEN,EXIT_ROW*LEN); else outtextxy(20,10,"The maze does not have a path"); /* 否则打印不存在信息*/void main()int i, j, c;srand(time(0);system("cls");for (i=0;i<N+2;i+)maze0i=1;mazei0=1;mazeN+1i=1;mazeiN+1=1; /* 将迷宫的四周设为1（墙壁） */printf("Would you

19、 like to input the maze by youself?nYes or No?");c = getchar();if(c='Y' | c= 'y') printf("Enter the %d * %d maze:n",N,N); /*手动输入*/for (i=1; i<N+1; i+) for(j=1; j<N+1; j+) scanf("%d",&mazeij); else printf("The maze is created by the computer:n&q

20、uot;); for (i=1; i<N+1; i+) for(j=1; j<N+1; j+) mazeij=rand()%2; mazeNN = 0; maze11 = 0; for(i=1;i<N+1;i+) for(j=1;j<N+1;j+) printf("%3d",mazeij); printf("n"); path(); /* 调用函数path() */getch();4测试方法4.1测试目的针对迷宫生成方式不同，本程序的测试分为两类：手动输入迷宫测试和计算机自动生成迷宫测试。另外，根据测试用例不同也可以分为两类：有解

21、迷宫测试无解迷宫测试。即检查是否可以自动生成或手动生成一个m*n的迷宫，并判断生成的迷宫图是否可从入口不经过重复点通过路“0”走向出口。4.2 测试输入a)按Y或y手动生成迷宫矩阵(有解迷宫)：先输入8*8的矩阵b)按任意键自动生成迷宫矩阵（有解迷宫）：c) 按任意键自动生成迷宫矩阵（无解迷宫）：4.3 正确输出不管是手动生成还是自动生成迷宫，走数字为零的点且不经过重复点走向出口。如果没有通路则失败。4.4 实际输出 a)给出的迷宫路线如图：b)对于自动生成电脑路线（有解迷宫），给出的迷宫路线：c) 对于有些自动生成的迷宫（无解迷宫），可能不可以完成走迷宫：4.5 错误原因走迷宫失败原因是从入

22、口通向出口的路上被墙“1”给堵住了，则无法走向出口。即没有一条从入口到出口的通路。5 分析与探讨5.1 测试结果分析 a. 手动生成的迷宫图是由一个8*8的矩阵构成的，这是由最大栈容量MAX_STACK_SIZE决定的，0为路，1为墙，并且可以上、下、左、右、左上、左下、右上、右下行走，且不会走已经走过的点。最终从左上入口点开始到右下出口点结束。b. 自动生成的迷宫图同样遵循迷宫行走法则。5.2 探讨与改进上述的实验代码及实验结果都是在vc中进行的。因为turbo c现在有很多人不用且我习惯用的是vc，所以我用vc写。教学中给的代码适合在turbo C中进行，从源代码到现在代码的改进以及为完成实验要求。需先在vc中安装graphics.h和graphics.lib文件。并修改一些方法如random(2)改成rand()%2，clrscr()改成system(“cls”