当前位置:首页 >> 教育学/心理学 >>

迷宫的求解

课程设计的名称:迷宫的求解问题
1. 问题描述:迷宫只有两个门,一个叫做入口,另一个叫做出口。把一只老鼠从一个无
顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁,对前进方向形成了多处障碍,在迷 宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题, 即找出从入口到出口的路径。

2. 基本要求:
(1)首先建立一个表示迷宫的数据结构; (2)要有试探方向和栈的设计; (3)不能重复到达某点,不能发生死循环;

3. 算法思想:
若当前位置可通,则纳入路径,继续前进;若当前位置不可通,则后退,换方向继续探索; 若四周均无通路,则将当前位置从路径中删去。

4. 模块划分:
(1)int maze[n1][n2]是首先建立一个迷宫的矩阵,0 为通路,1 为不通。 (2)main()函数将初始化 top[],使得所有的开始方向为左。 (3)采用回溯法不断地试探并且及时的纠正错误,使得能够找到正确的路径。

5.数据结构
(1)坐标点的结构定义如下: typedef struct node { int x; int y; int c; }linkstack; (2)迷宫的数据结构定义如下: maze[m][n] maze[i][j]=0 通路 maze[i][j]=1 不通

6. 源程序:
#include<stdio.h> #include<stdlib.h> #define n1 10 #define n2 10 typedef struct node { int x;//存 x 坐标 int y;//存 y 坐标 int c;//存该点可能的下点所在的方向,1 表示向右,2 向上,3 向左,4 向右 }linkstack; linkstack top[100];

//迷宫矩阵 int maze[n1][n2]={ 1,1,1,1,1,1,1,1,1,1, 0,0,0,1,0,0,0,1,0,1, 1,1,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,0, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1, }; int i,j,k,m=0; main() {//初始化 top[],置所有方向数向左 for(i=0;i<n1*n2;i++) {top[i].c=1;} printf("the maze is:\n"); //打印原始迷宫矩阵 for(i=0;i<n1;i++) {for(j=0;j<n2;j++) printf(maze[i][j]?"*":""); printf("\n"); } i=0; top[i].x=1; top[i].y=0; maze[1][0]=2; //回溯算法 do{ if(top[i].c<5)//还可以向前试探 { if(top[i].x==5&&top[i].y==9)//已经找到一个组合 {//打印路径 printf("The way %d is:\n",m++); for(j=0;j<=i;j++) {printf("(%d,%d)-->",top[j].x,top[j].y);} printf("\n"); //打印选出路径的迷宫 for(j=0;j<n1;j++) { for(k=0;k<n2;k++) {if(maze[j][k]==0)

printf(""); else if(maze[j][k]==2) printf("0"); else printf("*");} printf("\n"); } maze[top[i].x][top[i].y]=0; top[i].c=1; i--; top[i].c+=1; continue; } switch(top[i].c)//向前试探 { case 1: { if(maze[top[i].x][top[i].y+1]==0) {i++; top[i].x=top[i-1].x; top[i].y=top[i-1].y+1; maze[top[i].x][top[i].y]=2;} else{ top[i].c+=1;} break; } case 2: {if(maze[top[i].x-1][top[i].y]==0) {i++; top[i].x=top[i-1].x-1; top[i].y=top[i-1].y; maze[top[i].x][top[i].y]=2;} else{top[i].c+=1;} break;} case 3: {if(maze[top[i].x][top[i].y-1]==0) {i++; top[i].x=top[i-1].x; top[i].y=top[i-1].y-1; maze[top[i].x][top[i].y]=2;} else{ top[i].c+=1;} break;} case 4: {if( maze[top[i].x+1][top[i].y]==0) {i++; top[i].x=top[i-1].x+1; top[i].y=top[i-1].y;

maze[top[i].x][top[i].y]=2;} else{top[i].c+=1;} break;} } } else//回溯 { if(i==0) return 0;//已经找完所有解 maze[top[i].x][top[i].y]=0; top[i].c=1; i--; top[i].c+=1;} }while(1); }

7. 测试情况:
截图:

结果分析:
通过程序运行的结果可以看出, 此程序能够实现在有一个入口一个出口的情况下选择路径的 功能,并且就此程序而言,有多条路径可以选择。


相关文章:
迷宫的求解.doc
迷宫的求解 - 课程设计的名称:迷宫的求解问题 1. 问题描述:迷宫只有两个门,
迷宫问题求解讲解.doc
迷宫问题求解讲解 - 课程设计报告 课题名称: 姓学专班名: 号: 业: 级: 迷宫问题的求解及演示 计算机与信息学院 指导教师: 第 1 页共 17 页 数据结构课程...
迷宫求解.doc
迷宫求解 - 数据结构课程设计(详细步骤)... 迷宫求解_数学_高中教育_教育专区。数据结构课程设计(详细步骤) 《数据结构》 课程设计报告 课题名称: 迷宫问题、八皇后...
迷宫求解参考答案.txt
迷宫求解参考答案 - #include<stdio.h> #include&l...... (%d,%d)\n",e.ord,e.seat.x,e.seat.y); return OK; } //---迷宫求解的具体...
迷宫求解细节.doc
迷宫求解细节 - 数据结构课程设计 一、 需求分析 1.选题理由 本次课设我选择了迷宫问题, 迷宫求解是数据结构课程的一个经典问题, 迷宫问题要求寻找一条从入口到...
迷宫问题的求解.doc
迷宫问题的求解 - 【数据结构课程设计】C++环境下利用栈实现迷宫求解问题。... 迷宫问题的求解_IT/计算机_专业资料。【数据结构课程设计】C++环境下利用栈实现迷宫求解...
迷宫问题求解.doc
迷宫问题求解 - 数据结构实验迷宫问题求解 一、 实验内容: 利用队的结构实现迷宫求解问题。测试算法的迷宫如下图所示: 要求输入起始点的坐标,输出走出迷宫最短...
数据结构 迷宫求解.doc
数据结构 迷宫求解_调查/报告_表格/模板_实用文档。数据结构实验报告 迷宫求解C++ 【完成题目 3】迷宫求解 【问题描述】以一个 m*n 的长方阵表示迷宫,0 ...
求解迷宫问题 (c语言,很详细哦).doc
求解迷宫问题 (c语言,很详细哦) - 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是 “穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能...
迷宫求解实验报告.doc
\n"); continue; } } while(end.r>maze.r || end.c>maze.c); if(!MazePath(maze,start,end))//迷宫求解 printf("\n 没有路径!\n"); else ...
迷宫求解.doc
迷宫求解_计算机软件及应用_IT/计算机_专业资料。C++ C++大作业 解决问题:迷宫求解 班级:1401052 姓名:江岚 学号:14010520029 1 问题内容的描述随机产生一个 20*...
求解迷宫程序.doc
求解迷宫程序 - 求解迷宫程序: #include<iostream>
迷宫求解参考答案.txt
迷宫求解参考答案 - 迷宫问题(栈) 问题描述: 以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到...
迷宫问题的求解.doc
迷宫问题的求解_计算机软件及应用_IT/计算机_专业资料。数据结构实验 程序设计
数据结构 迷宫问题求解.doc
数据结构 迷宫问题求解 - 安徽大学计算机实验教学中心 1 学号 实验日期 专业
迷宫求解.ppt
迷宫求解 C语言教程ppt迷宫求解 C语言教程ppt隐藏>> 迷宫求解 c语言版 目录 头文件 Stack.h 主程序 maze.c 头文件 Stack.h 迷宫结构体 typedef struct{ int ...
迷宫求解.doc
迷宫求解 - #include <stdio.h> #include
迷宫求解.doc
迷宫求解 - #include <stdio.h> #include <malloc.h> #include <stdlib.h> #define M 8 // 迷宫行数(包括外墙) #defi...
数据结构C语言迷宫求解问题(有要求和源代码).doc
数据结构C语言迷宫求解问题(有要求和源代码) - 1、 迷宫求解 设计一个迷宫求解程序,要求如下: ? 以 M × N 表示长方阵表示迷宫,求出一条从入口到出口的...
迷宫问题(数据结构).txt
迷宫问题(数据结构) - 数据结构迷宫问题,八方向的。自动生成迷宫。... //迷宫数组中的元素类型 //--- 迷宫求解的具体算法 ---// Status MakeMaze(MazeType ma...