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

数数据据结结构构课课程程设设计计报报告告 深度与广度优先搜索：迷宫问深度与广度优先搜索：迷宫问 题题的设计的设计 目目录录 1 设计内容 .1 2 设计分析.1 3 设计实践 .3 4 测试方法 .4 5 程序运行效果.6 6 设计心得.8 7 附录.9 数据结构课程设计报告（2017） 深度与广度优先搜索：迷宫问题的设计深度与广度优先搜索：迷宫问题的设计 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。根据这个数组，就很容易计算出沿某个方向行走 的下一点的坐标。 1 深度与广度优先搜索：迷宫问题的设计 表 3.1 8 种方向 move 的偏移量 Name N NE E SE S SW W NW Dir 0 1 2 3 4 5 6 7 Move[dir].vert -1 -1 0 1 1 1 0 -1 Move[dir].horiz 0 1 1 1 0 -1 -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)，采用深度优先搜索算法，首先取出栈顶元素作为当前 2 数据结构课程设计报告（2017） 点，并从当前点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个 点压入栈，并将二维数组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- 标志路径是否发现| \*-------------------------------------------------------