迷宫问题求解
利用栈实现迷宫地求解
利用栈实现迷宫的求解 一、要解决的问题： 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 二：算法基本思想描述: 用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第n列元素置成“0”，表示迷宫的入口和出口走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序试探下一个位置； 用二维数组move记录4个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定： Px=x+move[i][0] Py=y+move[i][1] 如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索； 如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。 三：设计： 1：数据结构的设计： （1）定义三元数组元素的结构 typedef struct MazeDirect { int Dx; //行标 int Dy; //列标 int direct; //走到下一个坐标点的方向 }MazeDirect; （2）定义链表节点的结构组成 typedef struct LinkNode { elemtype data; //数据域 struct LinkNode *next; //指针域 }LinkNode; （3）定义链栈的头指针 typedef struct {
迷宫问题的求解
迷宫问题求解 一．问题描述： 请设计一个算法实现迷宫问题求解。 二．需求分析： 程序可实现用户与计算机的交互过程。在计算机显示提示信息后，可由用户输入迷宫的大小与形态，以“0”表示墙壁，以“1”表示通路。利用栈操作寻找一条从入口至出口的通路，最终输出带有路线的迷宫。 三．算法思想： 1.栈的设计： 用计算机解迷宫问题时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通则继续向前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，可以利用“栈”来求解迷宫问题。 2. 表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中0表示墙壁（不通），1表示通路，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化，用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为0。这样做可使问题简化，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 3 0 1 1 1 1 1 1 1 0 0 4 0 1 1 0 0 1 0 0 0 0 5 0 0 1 1 1 0 1 1 1 0 6 0 1 0 0 1 1 1 1 1 0 7 0 0 0 0 0 0 0 0 0 0 3. 试探方向： 在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，
迷宫求解问题资料
迷宫求解问题 摘要：用矩阵表示迷宫，将矩阵表示的迷宫转换成无向图，用邻接表存储。对无向图从入口结点开始广度优先搜索，用一个一维数组存储各个结点的前驱结点的编号，通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2，依次类推直到找到出口结点。 关键字：矩阵迷宫求解 一、需求分析 1.程序题目： 迷宫求解问题。迷宫是一个如下所示的m行n列的0-1矩阵，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到周围8个方向的任意一个无障碍的单元，编写程序给出一条通过迷宫的路径或者报告一个“无法通过”的信息。 入口->(0，0，0，1，0，0，0，1，0，0，0，1，0，0，1) (0，1，0，0，0，1，0，1，0，0，0，1，1，1，1) (0，1，1，1，1，1，0，1，0，0，1，1，1，0，1)
(1，1，0，0，0，1，1，0，1，1，0，0，1，0，1) (1，0，0，1，0，1，1，1，1，0，1，0，1，0，1) (1，0，1，0，0，1，0，1，0，1，0，1，0，1，0) (1，0，1，1，1，1，1，0，0，1，1，1，1，0，0) (1，1，1，0，1，1，1，1，0，1，0，1，0，1，0) (1，0，1，0，1，0，1，1，1，0，1，0，0，0，1) (0，1，0，1，0，1，0，0，0，1，1，0，0，1，0)->出口 2．程序说明及任务： 迷宫问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图C。 计算机走迷宫的方法是，采取一步一步试探的方法。每一步都从东开始，按顺时针对8个方向进行试探，若某方向上maze（x，y）=0，表示可以通行，则走一步；若maze（x，y）=1，表示不可以通行，须换方向再试，直到8个方向都试过；若maze （x，y）均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此，需设置一个栈，用于记录所走过的位置和方向（i,j,dir）。当退回一步时，从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和方向重新进栈，并走到新的位置。
利用栈实现迷宫的求解
利用栈实现迷宫的求解 一、要解决的四个问题： 1、表示迷宫的数据结构： 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫，maze[i][j]=0或1; 其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。 如图3.4表示的迷宫是一个6×8的迷宫。入口坐标为（1，1），出口坐标为（m，n）。 入口(1,1) 图 1 用maze[m+2][n+2]表示的迷 宫 迷宫的定义如下： #define m 6 /* 迷宫的实际行 */ #define n 8 /* 迷宫的实际列 */ int maze [m+2][n+2] 2 、试探方向： 在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x , y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move [ 4 ]中，在move 数组中，每个元 m n 素有两个域组成，x：横坐标增量，y：纵坐标增量。Move数组如图3所示。 move数组定义如下： typedef struct { int x //行 int y //列 } item item move[4] 这样对move的设计会很方便地求出从某点 (x，y) 按某一方向 v (0≤v≤3) 到达的新点（i，j）的坐标：i =x + move[v].x ，j = y + move[v].y 。 3．栈的设计： 当到达了某点而无路可走时需返回前一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为： 栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走
c语言迷宫问题的求解(栈和递归)
实验报告 【实验名称】项目一迷宫问题的求解 【实验目的】 1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体 的运用。 2.学会用栈或者递归方法解决迷宫问题。 【实验原理】 1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。 2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。 3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。 4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。 【实验内容】 1.需求分析 （1）问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。
（2）基本要求 （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。 2.概要设计 （1）栈的抽象数据类型 ADT Stack{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={
实验四：A星算法求解迷宫问题实验
实验四：A*算法求解迷宫问题实验 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解迷宫问题，理解求解流程和搜索顺序。 二、实验内容 迷宫问题可以表述为：一个二维的网格，0表示点可走，1表示点不可以走，点用（x，y）表示，寻找从某一个给定的起始单元格出发，经由行相邻或列相邻的单元格(可以通过的)，最终可以到达目标单元格的、所走过的单元格序列。在任一个单元格中，都只能看到与它邻近的4个单元格(如果位于底边，则只有3个；位于4个角上，则只有2个是否能通过)。 A*算法是人工智能中的一种搜索算法，是一种启发式搜索算法，它不需遍历所有节点，只是利用包含问题启发式信息的评价函数对节点进行排序，使搜索方向朝着最有可能找到目标并产生最优解的方向。它的独特之处是检查最短路径中每个可能的节点时引入了全局信息，对当前节点距终点的距离做出估计，并作为评价节点处于最短路线上的可能性的度量。 A*算法中引入了评估函数，评估函数为：f（n）=g（n）+h（n）其中：n是搜索中遇到的任意状态。g(n)是从起始状态到n的代价。h(n)是对n到目标状态代价的启发式估计。即评估函数f ( n) 是从初
始节点到达节点n 处已经付出的代价与节点n 到达目标节点的接近程度估价值的总和。 这里我们定义n点到目标点的最小实际距离为h（n）*，A*算法要满足的条件为：h（n）<=h（n）* 迷宫走的时候只能往上下左右走，每走一步，代价为1，这里我们采用的估价函数为当前节点到目标节点的曼哈顿距离，即：h（n）=|end.x –n.x|+ |end.y –n.y| 这里end表示迷宫的目标点，n表示当前点，很明显这里h（n）<=h（n）*。 g（n）容易表示，即每走一步的代价是1，所以利用f（n）=g（n）+h（n）这种策略，我们可以不断地逼近目标点，从而找到问题的解。 时间复杂度：m行n列的迷宫矩阵实现算法的时间复杂度为O(m*n). 实验结果：
回溯法之N皇后问题(C语言)
//回溯法之N皇后问题当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include 河南科技大学 课程设计报告 课程名称：算法设计与分析 设计题目：罗密欧与朱丽叶迷宫求解问题 院系：电子信息工程学院 专业：计算机科学与技术 班级：计算机092班 学生姓名: 学号:09************ 起止日期: 2011年5月28日 - 2011年6月3日指导教师:孙士保、张明川、冀治航 课程设计题目罗密欧与朱丽叶的迷宫问题 姓名*** 学号091040602** 班级092班系别电子信息工程学院专业计算机科学与技术 组别1人组长*** 组员*** 指导教师姓名孙士保、张明川、冀治航 课程设计目的 进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。 设计环境1. PC兼容机 2．Windows 2000/XP操作系统3．TC集成开发环境或其他C语言开发环境 课程设计要求和任务要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题； 2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存 到文件中； 3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 4．对系统进行功能模块分析、画出总流程图和各模块流程图； 5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单； 6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块； 7．所有程序需调试通过。 任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括： 1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线； 2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。 课程设计工作进度计划 序号起止日期工作内容 1 下发任务书，分组，选定课题，查阅相关资料 2 总体设计，划分模块 3 编制源程序 4 上机调试，修改、完善系统 5 程序检查 6 撰写说明书 #include if(s->top - s->base >= s->size) { s->base = (lujing *)realloc(s->base, (s->size+INCREMENT)*sizeof(lujing)); if(!s->base) return -1; s->top = s->base+s->size; s->size += INCREMENT; } *s->top++ = e; return 0; } int pop(SqStack *s,lujing *e) { if(s->top == s->base) return -1; *e = *(--s->top); return 0; } int isEmpty(SqStack *s) { if(s->base == s->top) return 1; else return 0; } int pass( Maze maze,zuobiao dqzb) { if (maze.sz[dqzb.r][dqzb.c]==1) return 1; // 如果当前位置是可以通过，返回1 else return 0; // 否则返回0 } void footPrint(Maze &maze,zuobiao dqzb) { maze.sz[dqzb.r][dqzb.c]=9; } void markPrint(Maze &maze,zuobiao dqzb) { maze.sz[dqzb.r][dqzb.c]=4; } zuobiao nextPos(zuobiao dqzb, int Dir) { 课程设计报告 课题名称：迷宫问题的求解及演示姓名： 学号： 专业：计算机与信息学院 班级： 指导教师： 数据结构课程设计任务书针对本课程设计，完成以下课程设计任务书： 1.熟悉系统实现工具和上机环境。 2.根据课程设计任务，查阅相关资料。 3.针对所选课题完成以下工作： （1）需求分析 （2）概要设计 （3）详细设计 （4）编写源程序 （5）静态走查程序和上机调试程序 4.书写上述文档和撰写课程设计报告 目录 第一部分课程设计任务书 (1) 第二部分课程设计报告 (2) 第一章课程设计内容和要求 (4) 2.1 问题描述 (4) 2.2 需求分析 (4) 第二章课程设计总体方案及分析 (4) 3.1 概要设计 (7) 3.2 详细设计 (7) 3.3 调试分析 (10) 3.4 测试结果 (10) 第三章设计总结 (13) 4.1课程设计总结 (13) 4.2参考文献………………………………………………… 4.3 附录(源代码) (14) 第二部分课程设计报告 第一章课程设计内容和要求 2.1问题描述： 迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序，求出一条从入口到出口的路径并显示之（结果若能用C的绘图函数显示更好） 2.2需求分析： 1．要求设计程序输出如下： (1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏 幕上显示出来； （2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。 （3）用一种标志（如数字8）在迷宫中标出该条通路； （4）在屏幕上输出迷宫和通路； （5）上述功能可用菜单选择。 2.迷宫的建立： 迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述， 3.迷宫的存储： 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型 实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制 一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) 皇后问题 2.测试数据0.退出**"< 算法设计与分析课程设计罗密欧与朱丽叶的迷宫问题设计分析测试报告 程序算法设计说明书 一、前言 1、题目：罗密欧与朱丽叶的迷宫问题。 罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这些道路。 2、程序编制环境相关说明 硬件：装有windows操作系统的计算机 软件：Visual C++ 2008 二、程序主要算法设计分析说明 1、算法设计思路 用回溯法解迷宫问题时，用排列树表示其解空间比较合适。可行性约束函数减去不满足约束条件（x,y,z）已越界的子树。在排列树的第i+1层节点z处用board[z][x][y]记载所在的房间。当bool stepok(int x,int y,int z)返回为false时，以z为根的子树中所有子树都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪枝。 算法调用递归方法void backtrack(int dep,int x,int y,int di)实现回溯搜索。void backtrack (int dep,int x,int y,int di)搜索排列树中第dep层子树。数组board[0][x][y]记录排列树中的节点信息。dirs记录当前节点对应的转弯数， best记录最少转弯数。 在算法void backtrack (int dep,int x,int y,int di)中，当i>n时，算法搜索至叶节点，其相应的转弯数dirs。如果dirs>best,则表示当前解优于最优解，此时更新best。当i≤n时，当前扩展节点位于是排列树的第i-1层。此时算法选择下一个要搜索的方向，以深度优先的方式递归地对相应子树进行搜。对于不满足上界约束的节点，则减去相应子树。 算法void backtrack (int dep,int x,int y,int di)动态地生成问题的解空间树。 时间复杂度为整个状态空间，即迷宫大小，O(m*n) 课程设计说明书 课程名称＿＿软件专题训练＿＿＿＿ 题目罗密欧与朱丽叶迷宫求解问题＿ 院系＿电子信息工程学院计算机系＿ 班级＿计算机科学与技术103班＿＿ 学生姓名＿＿＿＿＿＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 课程设计任务书 课程名称＿＿算法设计与分析＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系＿电子信息工程学院计算机系＿ 班级＿＿＿计算机103班＿＿＿＿＿ 学生姓名＿＿＿＿魏鹏超＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 河南科技大学 课程设计报告 课程名称＿＿软件专题训练＿＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系：电子信息工程学院计算机系 专业：计算机科学与技术 班级：计算机10级 学生姓名:学号: 起止日期: 2012年5月21日~ 2012年5月27日指导教师:孙士保、冀治航 目录 第一章需求分析 (4) 1.1课程设计题目 (4) 1.2 课程设计任务及要求 (4) 1.3运行环境及开发工具 (4) 第二章概要设计 (5) 2.1系统流程图 (5) 第三章详细设计 (6) 3.1函数划分 (6) 3.2函数之间的关系 (6) 第四章系统调试与操作说明 (7) 4.1系统调试及操作说明 (7) 第五章课程设计总结体会 (8) 5.1课程设计总结 (8) 5.2致谢 (8) 5.3参考文献 (8) 第一章需求分析 1.1课程设计题目 罗密欧与朱丽叶的迷宫问题 1.2 课程设计任务及要求 1、对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽 叶的所有最少转弯道路 2、程序能够演示一条罗密欧找到朱丽叶的路线过程等 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。 1.3运行环境及开发工具 硬件：装有windows操作系统的计算机 软件：Visual C++6.0 数据结构实验报告 题目：用栈解决迷宫问题 ．需求分析 1．以结构体 Maze 表示迷宫，其中 pos 表示该位置是否有障碍； freq 记录该位置被经过的次数；数组 move 表示下一步的方向。 2. 本程序自动随机生成一个12 × 12大小的迷宫，字符“ H”表示有障碍，空符表示通 路。 3. 迷宫的入口为左上角，出口为右下角。 4. 本程序只求出一条成功的通路。 .概要设计 为了实现上述操作，以栈为存储结构。 本程序包含三个模块： 1)主程序模块 :实现人机交互。 2)迷宫生产模块:随机产生一个12× 12的迷 宫。 3)路径查找模块：实现通路的查找。 4)求解迷宫中一条通路的伪代码： do{ 若当前位置可同，则{ 将当前位置插入栈顶；若该位置是出口位置，则结束；否则切换当前位置的东临方块为新的当前位置；} 否则 { 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的的当前位置为沿顺时针 方向旋转找到的栈顶位置的下一相邻块若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈 至栈空。 } } } while( 栈不空 ) 三. 详细设计栈的设计： typedef struct { Node *base,*top; int length; }Stack; Stack *initstack(); // 初始化栈 void printstack(Stack *s); // 打印栈 Status destroy(Stack *); // 销毁整个栈 Status deltop(Stack *s); // 出栈 Status pushelem(Stack *,ElemType ,ElemType); // 进栈 1. 主程序模块： int main() { printf(" 随机产生一个12× 12 的迷宫， X 字符表示障碍，空符表示通路： \n"); Maze a[N][N]; makemaze(a); printf(" 输入回车键显示路径 ,* 字符表示路径。 \n"); getchar(); findpath(a); while(1); return 0; 算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013.12.3 姓名：杜茂鹏 班级：计科1101 学号：0909101605 一、实验内容及要求 在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法中的应用 三、算法分析 1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。 2.算法模块简要分析 用数组存储皇后的位置，将i设置为0. Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。 Int print(*x,n):打印皇后解的空间。 Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。 Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时， sum++；输出该组可行解的个数和位置的矩阵。并且i--，回溯到上一层继续搜索可行解。 四、运行结果及分析 1、三皇后没有可行解 2、 2.4个皇后有2个可行解 3.5皇后有10个可行解 五、源代码 #include 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,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,1}, {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} }; 伪代码： c语言描述如下： void mgpath() /*路径为:(1,1)->(M-2,N-2)*/ { int i,j,di,find,k; top++; /*初始方块进栈*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while (top>-1) /*栈不空时循环*/ { i=Stack[top].i; j=Stack[top].j; di=Stack[top].di; if (i==M-2 && j==N-2) /*找到了出口,输出路径*/ { printf("迷宫路径如下:\n"); for (k=0;k<=top;k++) { printf("\t(%d,%d)",Stack[k].i,Stack[k] .j); if ((k+1)%5==0) printf("\n"); } 算法分析与设计论文论文题目：回溯法解迷宫问题 作者姓名陈相艺 任课教师王松 学院班级计算机学院计自1101班 学号201126100404 提交日期2013年6月10日 回溯法解迷宫问题 陈相艺 （计算机+自动化1101 201126100404） 摘要：迷宫的存储结构以二维数组来存储，用0，1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法，其实迷宫问题是一种特殊形式图的问题，因此，迷宫总量可转化为图的问题来解决。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.本文采用回溯法求解迷宫路径，算法用到数据结构中的栈。 关键词：迷宫；二位数组；回溯法；栈；矩阵。 1.前言 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子放入,在盒中设立了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口处放置一快奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走通迷宫的线路.设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 2.迷宫问题的算法思想及研究 迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷宫路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。 为了表示迷宫，设置一个数组，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，数组如下所示： int mg[10][10] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,1,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,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,1}, {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}}; （可根据自己喜好，改变迷宫的大小和通道安排。） 对于迷宫中每个方块，都有上下左右四个方块相邻，第i行第j列的当前方块的位置为(i,j)， 数组栈解决迷宫问题 /*[迷宫问题]分析: 1.建立一个路径栈path_stack,其中栈内有x,y用来记录坐标 东南西北4个方向，分用用east,south,west,north表示 初始位置x,y入栈 { 如果坐标[x][y+1]东探测为0时，入栈并标记当前坐标为2表示已行走过 否则坐标[x+1][y]南探测为0时，入栈............................. 否则坐标[x][y-1]西探测为0时，入栈.............................. 否则坐标[x-1][y]北探测为0时，入栈.............................. 否则坐标都不为0，此时探测到死角，这时就须要返回走 即出栈返回x,y新坐标 ......继续探测为0的出口 每执行一次判断终点坐 } !!!严重注意:本程序在Turboc C++中运行时没有异常，在Visual C++ 6.0中编译也成功，运行时全部正常,但是得不到正确答案，原因是Visual C++ 6.0 结构体类型返回有误，该变量虽返回，但值没有返回，所以 只须按结构体指针类型返因即可，TMD从凌晨1点卡到凌晨2点半 *///程序编写: #include { int x; int y; }path_stack[MAX]; int path_top=-1; int path_isEmpty() //栈的方法函数{ if (path_top==-1) return 1; else return 0; } int path_push(int x,int y) { if (path_top>=MAX) { printf("Stack go beyond!\n"); return 0; } else { path_top++; path_stack[path_top].x=x; path_stack[path_top].y=y; return 1; } 数据结构课程设计——迷宫问题求解代码 问题描述及要求： 迷宫问题求解 输入： 第一行n，m表示迷宫大小n*m 之后有n行m列，全由01组成，0表示路，1表示墙 入口设为(0,0) 出口设为(n-1,m-1) 输出： 输出从入口到出口的所有不同解，每组解的第一行打印一个数表示第几组解，之后k行表示路径，如： 1 (0,0) (0,1) (1,1) 代码部分（已测试，可直接运行）： #include Point tmp; tmp.x=x+oper[i][0]; tmp.y=y+oper[i][1]; path[len]=tmp; step[tmp.x][tmp.y]=1; dfs(tmp.x,tmp.y,len+1); step[tmp.x][tmp.y]=0; } } void work(){ step[0][0]=1; Point cur; cur.x=0; cur.y=0; path[0]=cur; dfs(0,0,1); } int main(){ scanf("%d%d",&n,&m); for(int i=0;i算法实验报告：罗密欧与朱丽叶迷宫求解
栈的应用-迷宫问题-数据结构(C语言版)-源代码(直接运行)
迷宫问题求解
算法实验 递归回溯解八皇后问题
迷宫问题
罗密欧与朱丽叶迷宫求解问题
迷宫问题实验报告用栈解决迷宫问题
n皇后问题算法实验报告
求解迷宫问题
回溯法解迷宫问题
数组栈解决迷宫问题
数据结构迷宫问题的C 代码