数据结构与算法之迷宫.doc

数据结构预算法迷宫问题哈尔滨工业大学 金字塔的小蜗牛一、问题描述：编写一个程序：随机生成一个20 x 20的迷宫，并找到一条从入口到出口的路线。要求：(1)“迷宫”大小可变，模式随机。(2)迷宫没有通路时，给出警告；有通路时，任给一条具体路径。(3)分析算法的效率。二、算法基本思想：通过产生随机数的方式生成一个只含0和1的二维数组，用这个二维数组来表示迷宫，其中数字1表示通路，数字0表示围墙。设定好迷宫的入口和出口，采用递归的方法找到一条走出迷宫的路线图，数组my_maze存有正寻找的路线图，在找路线图的运行过程中没有出口的路线图即被后来的路线覆盖，直到找到能走出迷宫的路线图，然后将my_maze中的元素赋给target_maze。最终将路线图target_maze打印出来。三、主要数据结构（编程环境：code blocks）：1、二维数组一个表示迷宫的二维数组mazeij，相关操作有：(1) 建立二维数组，赋初值。(2) 数组以指针形式在各函数中传递。(3) 改变数组中某个元素的值。2、指针运算 函数move_to、print_maze1、print_maze2都含有指针作为函数中的变量进行调用。3、递归运算 在寻找迷宫路径的时候，用到了递归运算。在程序中即从一个点搜寻下一个点的反复过程中不断调用move_to函数自身，最终寻找到走出迷宫的路径。四、主要函数功能：1、produce_maze()函数功能：随机生成一个20 x 20的二维迷宫。2、move_to(int _i,int _j, int (*in_maze)MAX_COL, int count)函数功能：采用递归思想找到一条走出迷宫的路径。3、print_maze1(int (*maze)MAX_COL)函数功能：打印出生成的迷宫图案。4、print_maze2(int (*maze1)MAX_COL,int (*maze2)MAX_COL)函数功能：打印出附有路径的迷宫图案。五、一个算例：程序运行的一个结果如下所示： 六、算法分析：程序运行时间主要在于不断的由一个点往下寻找另一个点的过程，对于一个m*n的迷宫来说，其时间复杂度不会超过（m*n）4.但实际运行过程中会节约很多时间，因为程序寻找路径时以向下、向右为先。在空间占用上，因为保存寻找路径的my_maze采用不断覆盖的方式，只将最终成功的路线赋给target_maze，所以在一定程度上节省了运行与存储空间。附录：C语言源代码#include #include #include #include /* 定义迷宫的大小*/#define MAX_COL 9#define MAX_ROW 9#define TRUE 1#define FALSE 0#define IS_USABLE(a, b) (a = 0 & a = 0 & b MAX_COL) & mazeab & (!my_mazeab)static int mazeMAX_ROWMAX_COL;static int target_mazeMAX_ROWMAX_COL;static void init_maze();static int move_to(int i, int j, int (*maze)MAX_COL, int count);static void print_maze(int (*maze)MAX_COL);static void init_maze() int i, j; srand(unsigned) time(NULL); for (i = 0; i MAX_ROW; i+) for (j = 0; j MAX_COL; j+) mazeij = (int) (rand() % 2); maze10 = 1; /* 设定迷宫入口 */ mazeMAX_ROW - 1MAX_COL - 2 = 1; /* 设定迷宫出口 */static int move_to(int _i,int _j, int (*in_maze)MAX_COL, int count) int my_mazeMAX_ROWMAX_COL, i, j; if (!in_maze) for (i = 0; i MAX_ROW; i+) for (j = 0; j MAX_COL; j+) my_mazeij = 0; else for (i = 0; i MAX_ROW; i+) for (j = 0; j MAX_COL; j+) my_mazeij = in_mazeij; my_maze_i_j = count; /* reach the end point */ if (_i = MAX_ROW - 1 & _j = MAX_COL - 2) for (i = 0; i MAX_ROW; i+) for (j = 0; j MAX_COL; j+) target_mazeij = my_mazeij; return TRUE; if (IS_USABLE(_i - 1, _j) if (move_to(_i - 1, _j, my_maze, count + 1) return TRUE; if (IS_USABLE(_i + 1, _j) if (move_to(_i + 1, _j, my_maze, count + 1) return TRUE; if (IS_USABLE(_i, _j - 1) if (move_to(_i, _j - 1, my_maze, count + 1) return TRUE; if (IS_USABLE(_i, _j + 1) if (move_to(_i, _j + 1, my_maze, count + 1) return TRUE; return FALSE;static void print_maze(int (*maze)MAX_COL) int i, j; printf( ); for (i = 0; i MAX_ROW; i+) for (j = 0; j MAX_COL; j+) if (mazeij != 0) if (mazeij10) printf(%d , mazeij); else printf(%d , mazeij); else printf( ); printf( n ); int main() while (1) init_maze(); prin