深度与广度优先搜索：迷宫问题的设计.doc

数据结构课程设计报告（2017）

数据结构课程设计报告

深度与广度优先搜索：迷宫问题的设计

1

目 录
1 设计内容 1
2 设计分析 1
3设计实践 3
4测试方法 4
5 程序运行效果 6
6 设计心得 8
7 附录 9

深度与广度优先搜索：迷宫问题的设计
1 设计内容
一般的迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。迷宫问题求解的目标是寻找一条从入口点到出口点的通路。
例如，可以设计一个8*8矩阵maze[8][8]来表示迷宫，如下所示：
0 1 0 0 0 0 1 1
0 0 0 1 0 0 1 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 1 1 1 1 1 0
1 0 0 1 1 0 0 0
1 0 1 0 0 0 1 1
1 0 1 1 0 1 0 0
左上角maze[0][0]为起点，右下角maze[7][7]为终点；设“0”为通路，“1”为墙，即无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上，下，左，右，左上，左下，右上，右下”8个方向行走。
设计一个程序，能自动生存或者手动生成这样一个8*8矩阵，针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。如果不能，指出；如果能，用图形界面标出走出迷宫的路径。
2 设计分析
首先明确题目中的已知条件：
（1） 迷宫是一个8*8大小的矩阵。
（2） 从迷宫的左上角进入，右下角为迷宫的终点。
maze[i][j]=0代表第i+1行第j+1列的点是通路；maze[i][j]=1代表该点是墙，无法通行。
（3） 迷宫有两种生成方式：手工设定和自动生成。
（4） 当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8个方向。
要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组maze[N+2][N+2]来表示这个迷宫，其中N为迷宫的行，列数。当值为“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以由行号row和列号col表示。
为什么指定maze[N+2][N+2]来表示迷宫，而不是使用maze[N][N]来表示迷宫？原因是当老鼠跑到迷宫的边界点时就有可能跳出迷宫，而使用maze[N+2][N+2]就可以把迷宫的外面再包一层“1”，这样就能阻止老鼠走出格。
老鼠在每一点都有8种方向可以走，分别是：North，NorthEast，East，SouthEast，South，SouthWest，West，NorthWest。可以用数组move[8]来表示在每一个方向上的横纵坐标的偏移量，见表3.1。根据这个数组，就很容易计算出沿某个方向行走的下一点的坐标。

表3.1 8种方向move的偏移量

Name
Dir
Move[dir].vert
Move[dir].horiz
N
0
-1
0
NE
1
-1
1
E
2
0
1
SE
3
1
1
S
4
1
0
SW
5
1
-1
W
6
0
-1
NW
7
-1
-1

迷宫问题可以用深度优先搜索方法实现。当老鼠在迷宫中移动的时候，可能会有多种移动方向。程序需要记录并用栈来保存当前点的坐标，然后任意任取一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当在当前各方向上走不通时可以返回上一个点，然后选择另一个方向前进。
可定义element结构用于存储每一步的横纵坐标和方向。
Typedef struct{
short int row;
short int col;
short int dir;
}element;
element stack[MAX_STACK_SIZE]；
根据表3.1 可推算出每次移动后的坐标。设当前点的坐标是（row,col），移动方向是dir,移动后的点是next,则有
next_row=-row+move[dir].vert;
next_col=col+move[dir].horiz;
可用另一个二维数组mark[N+2][N+2]来记录哪些点已经被访问过。当经过点maze[row][col]时，相应地将mark[row][col]的值从0置1。
本程序支持自动生存迷宫。利用random（2）函数可随机产生0或1，来支持迷宫的自动生存。注意maze[N][N]和maze[1][1]一定要等于0，因为它们分别是起点和终点。
如果找到了一条走出迷宫的路径，则需要在屏幕中打印出如图3.5所示格式的信息。这里要用到graphices.h，即TC中的图形库。
程序的主要函数如下：
·函数void add(int *top,element item)，将当前步的信息item压入到作为全局变量的栈stack(栈顶为top)中。
·函数elemrnt delete(int *top)，返回stack中栈顶的元素。
·函数void path(void)，采用深度优先搜索算法，首先取出栈顶元素作为当前点，并从当前点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个点压入栈，并将二维数组mark中对应的值改为1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了，并且这个点不是终点，则这个点的上一个点会从栈中被抛出，从而“回溯”到上一个点；当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。
3设计实践
3.1结构体记录水平和垂直的偏移量
typedef struct {
short int vert;
short int horiz;
}offsets;

offsets move[8]; /* 8个方向的move */

int maze[N+2][N+2]; /*二维数组记录迷宫*/
int mark[N+2][N+2]; /*记录迷宫中每点是否可到达*/
int EXIT_ROW = N, EXIT_COL = N;

3.2输出走出迷宫的路径
void path(void)
{
int i, j, k, row, col, next_row, next_col, dir, found = FALSE;
int gd=VGA;
int gm=VGAHI;

/*--------------------------------------------------------------*\
| i ---> 用来循环计数 |
| row , col ---> 当前位置的坐标 |
| next_row ---> 移动后的位置的横坐标 |
| next_col ---> 移动后的位置的纵坐标 |
| dir ---> 移动的方向 |
| found ---> 标志路径是否发现 |
\*--------------------------------------------------------------*/

element position;
int top = 0;
mark[1][1] = 1; /* maze[1][1]已经被走过了*/
stack[0].row = 1;
stack[0].col = 1;
stack[0].dir = 1; /*第一步的状态*/
move[0].vert = -1; move[0].horiz = 0 ;
move[1].vert = -1; move[1].horiz = 1 ;
move[2].vert = 0 ; move[2].horiz = 1 ;
move[3].vert = 1 ; move[3].horiz = 1 ;
move[4].vert = 1 ; move[4].horiz = 0 ;
move[5].vert = 1 ; move[5].horiz = -1;
move[6].vert = 0 ; move[6].horiz = -1;
move[7].vert = -1; move[7].horiz = -1;

initgraph(&gd,&gm,""); /* 指定了八个方向*/

/*---------------------------------------------------------------------------*\
| 主要算法描述: |
| 当stack不为空,移动到stack顶部的位置 |
| 试着向各个方向移动，如果可以移动就移动到 |
| 下一个位置并把它标志成1。 |
| 然后保存状态并加入到stack中 |
| 如果路径被破坏，或者不存在，就将其删除 |
| 并返回到上一点继续遍历其他方向的点 |
| 直到一条路径被发现。 |
\*-----------------------------------------------------------------------------*/

4测试方法
针对迷宫生成方式不同，本程序的测试分为两类：手动输入迷宫测试和计算机自动生成迷宫测试。另外，根据测试用例类型不同也可分为两类：有解迷宫测试和无解迷宫测试。
下面给出两个测试用例。

测试用例1（有解迷宫）：
0 1 1 1 1 0 1 0
0 0 0 1 0 1 0 1
1 0 1 0 0 1 1 0
1 0 1 1 0 1 0 0
1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1
0 1 0 1 0 1 1 1
1 1 1 1 0 0 0 0

其期望输出结果如图所示。

测试用例2;（无解迷宫）
0 1 0 0 0 1 1 1
1 0 0 1 1 0 1 0
0 0 1 0 1 1 0 1
1 0 1 0 0 1 0 0
0 0 0 1 0 1 1 1
0 0 1 0 1 1 0 0
0 0 0 0 0 1 0 0
0 1 0 1 1 1 1 0

其期望输出结果如图所示。

5 程序运行效果
测试用例1（有解迷宫）：
0 1 1 1 1 0 1 0
0 0 0 1 1 1 0 1
1 0 1 0 0 1 1 0
1 0 1 1 0 1 0 0
1 0 0 1 0 1 1 0
0 1 1 0 1 1 1 1
0 1 0 1 0 1 1 1
1 1 1 1 0 0 0 0

其期望输出结果如图所示。

测试用例2;（无解迷宫）
0 1 0 0 0 1 1 1
1 0 1 1 0 0 1 0
0 1 1 0 0 1 1 1
1 0 1 1 0 0 0 0
0 1 0 1 0 1 1 0
0 1 1 0 1 0 0 0
0 0 1 1 0 0 1 1
1 1 0 1 0 1 1 0

其期望输出结果如图所示。

6 设计心得
通过这五天的课程设计里，也让我从中有所获，此次数据结构课程设计使我对深度和广度优先搜索有了更加深刻的了解，迷宫问题的课程设计就是充分的利用深度和广度优先搜索的有关知识。
刚开始用C语言编写，碰到了一个很大的问题，调试了很多次，在VC里执行不出来。“#include<graphics.h>”，这其实是TC里的一个图形库，在VC里编译时不行的，会显示有一个错误。但在TC里也碰到问题了，代码不能完全输入到编辑器中，导致最后还是无法运行。最后找了相关的代码，安装了相关图形文件进去，试了试，终于运行成功。
这次课程设计让我受益匪浅，对数据结构也有进一步的理解和认识。但也让我认识到我还有很多的不足，今后需要多实践和学习，提高能力和熟练应用。

7 附录
#include <stdio.h>
#include <stdlib.h>
#include <graphics.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;

element stack[MAX_STACK_SIZE];

/******结构体记录水平和垂直的偏移量******/
typedef struct {
short int vert;
short int horiz;
}offsets;

offsets move[8]; /* 8个方向的move */

int maze[N+2][N+2]; /*二维数组记录迷宫*/
int mark[N+2][N+2]; /*记录迷宫中每点是否可到达*/
int EXIT_ROW = N, EXIT_COL = N;

/******在栈中加入一个元素******/
void add(int *top, element item)
{
if (*top >= MAX_STACK_SIZE - 1)
{
printf("The stack is full!\n");
return;
}
stack[++*top] = item;
}

/******返回栈中顶部的元素******/
element delete(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=VGAHI;

/*--------------------------------------------------------------*\
| i ---> 用来循环计数 |
| row , col ---> 当前位置的坐标 |
| next_row ---> 移动后的位置的横坐标 |
| next_col ---> 移动后的位置的纵坐标 |
| dir ---> 移动的方向 |
| found ---> 标志路径是否发现 |
\*--------------------------------------------------------------*/

element position;
int top = 0;
mark[1][1] = 1; /* maze[1][1]已经被走过了*/
stack[0].row = 1;
stack[0].col = 1;
stack[0].dir = 1; /*第一步的状态*/
move[0].vert = -1; move[0].horiz = 0 ;
move[1].vert = -1; move[1].horiz = 1 ;
move[2].vert = 0 ; move[2].horiz = 1 ;
move[3].vert = 1 ; move[3].horiz = 1 ;
move[4].vert = 1 ; move[4].horiz = 0 ;
move[5].vert = 1 ; move[5].horiz = -1;
move[6].vert = 0 ; move[6].horiz = -1;
move[7].vert = -1; move[7].horiz = -1;

initgraph(&gd,&gm,""); /* 指定了八个方向*/

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

position = delete(&top); /*删除stack中的元素*/

row = position.row;
col = position.col;
dir = position.dir;

while (dir < 8 && !found) {

next_row = row + move[dir].vert;
next_col = col + move[dir].horiz;

if (next_row == EXIT_ROW && next_col == EXIT_COL)
found = TRUE; /*发现路径*/

else if ( !maze[next_row][next_col] &&
!mark[next_row][next_col])
/*如果这点没有被走过并且可以走*/
{
mark[next_row][next_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(MAGENTA);
outtextxy(j*LEN-2,k*LEN-2,maze[k][j]?"1":"0");
}
if (found)
{ /* 如果发现路径，则打印出来*/
outtextxy(20,10,"The path is:");
setcolor(YELLOW);
for (i=0; i <top;i++)
{
line(stack[i].col*LEN, stack[i].row*LEN,stack[i+1].col*LEN,stack[i+1].row*LEN);
}
line(stack[i].col*LEN, stack[i].row*LEN,col*LEN,row*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;
randomize();
clrscr();
for (i=0;i<N+2;i++)
{
maze[0][i]=1;
maze[i][0]=1;
maze[N+1][i]=1;
maze[i][N+1]=1;
} /* 将迷宫的四周设为1（墙壁） */

printf("Would you 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",&maze[i][j]);
}
}
else
{
printf("The maze is created by the computer:\n");
for (i=1; i<N+1; i++)
for(j=1; j<N+1; j++)
{
maze[i][j]=random(2);
}
maze[N][N] = 0;
maze[1][1] = 0;
for(i=1;i<N+1;i++)
{
for(j=1;j<N+1;j++)
printf("%3d",maze[i][j]);
printf("\n");
}
}
path(); /* 调用函数path() */
getch();
}

11