数据结构与算法之迷宫_第1页
数据结构与算法之迷宫_第2页
数据结构与算法之迷宫_第3页
数据结构与算法之迷宫_第4页
数据结构与算法之迷宫_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、.数据结构预算法迷宫问题哈尔滨工业大学 金字塔的小蜗牛一、问题描述:编写一个程序:随机生成一个20 x 20的迷宫,并找到一条从入口到出口的路线。要求:(1)“迷宫”大小可变,模式随机。(2)迷宫没有通路时,给出警告;有通路时,任给一条具体路径。(3)分析算法的效率。二、算法基本思想:通过产生随机数的方式生成一个只含0和1的二维数组,用这个二维数组来表示迷宫,其中数字1表示通路,数字0表示围墙。设定好迷宫的入口和出口,采用递归的方法找到一条走出迷宫的路线图,数组my_maze存有正寻找的路线图,在找路线图的运行过程中没有出口的路线图即被后来的路线覆盖,直到找到能走出迷宫的路线图,然后将my_m

2、aze中的元素赋给target_maze。最终将路线图target_maze打印出来。三、主要数据结构(编程环境:code blocks):1、二维数组一个表示迷宫的二维数组mazeij,相关操作有:(1) 建立二维数组,赋初值。(2) 数组以指针形式在各函数中传递。(3) 改变数组中某个元素的值。2、指针运算 函数move_to、print_maze1、print_maze2都含有指针作为函数中的变量进行调用。3、递归运算 在寻找迷宫路径的时候,用到了递归运算。在程序中即从一个点搜寻下一个点的反复过程中不断调用move_to函数自身,最终寻找到走出迷宫的路径。四、主要函数功能:1、produ

3、ce_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

4、的迷宫来说,其时间复杂度不会超过(m*n)4.但实际运行过程中会节约很多时间,因为程序寻找路径时以向下、向右为先。在空间占用上,因为保存寻找路径的my_maze采用不断覆盖的方式,只将最终成功的路线赋给target_maze,所以在一定程度上节省了运行与存储空间。附录:C语言源代码#include <stdio.h>#include <stdlib.h>#include <time.h>#include <memory.h>/* 定义迷宫的大小*/#define MAX_COL 9#define MAX_ROW 9#define TRUE 1#d

5、efine FALSE 0#define IS_USABLE(a, b) (a >= 0 && a < MAX_ROW) && (b >= 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)

6、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 mo

7、ve_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; /* rea

8、ch 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 +

9、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 (mazeij<10) printf("%d ", mazeij); else printf("%d ", mazeij); else printf(" "); printf(" n "); int main() while (1) init_maze(); printf("生成的迷宫为 :n"

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论