当前位置:首页 >> 计算机软件及应用 >>

编程题迷宫求解

迷宫求解问题

摘 要:用矩阵表示迷宫,将矩阵表示的迷宫转换成无向图,用邻接表存储。对无向图从入 口结点开始广度优先搜索, 用一个一维数组存储各个结点的前驱结点的编号, 通过出口结点 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) 。当退回一步时,从栈中退出一个元素,以便在上一个 位置的下一个方向上探测,如又找到一个行进方向,则把当前位置和方向重新进栈,并走到 新的位置。 若探测到位置(m,n) ,则已经到达迷宫的出口,可以停止探测,输出存在栈中的路径; 如果在某一位置的 8 个方向上堵塞,则退回一步,继续探测;如果已退到迷宫的入口(栈中 无元素) ,则表示此迷宫无路径可走。

二、概要设计

主要思想: 1. 2. 3. 4. 5. 6. 用矩阵表示的迷宫; 将矩阵表示的迷宫转换成无向图,用邻接表存储; 对无向图从入口结点开始广度优先搜索; 用一个一维数组存储各个结点的前驱结点的编号; 通过出口结点 Vn 找到其前驱结点 Vn-1,再通过 Vn-1 找到 Vn-2; 依次类推直到找到出口结点。

基本设计算法: 1. 设置数组 maze[MAX][MAX]来模拟迷宫, 2. maze [i][j]=0 表示该方格所在的位置可通行, A[i][j]=1 则表明该位置不能通行;

3. 定义无向图 G,迷宫的规格(行、列)存放在 G.rownum、G.colnum 中,其结点数同迷 宫(数组 maze [MAX][MAX])的方格个数。 4. 每一个结点的邻接结点为其相邻(从点在数组 maze [][]中所处的位置的角度)的八个点 中值为 0 的点, 按结点的顺序依次找出每一个点的邻接点, 此即完成迷宫图的数组表示转化 为无向图表示,G 用邻接表存储; 5. 采用图的广度优先遍历的方法,从入口结点开始遍历,直到碰到出口结点为止。并设 置 record 数组来记录结点 i 在广度优先遍历过程中的前驱结点的编号 record[i]; 6. 这样(record[i],i)表示存在从结点 record[i]到 i 的边,这样就可以从出口顶点在图中的编号 回溯出口顶点,如此,一条从入口到出口的最短路径就找到了。在定义 record 数组是将所有初 始值设为-1,只是为了判断是否存在从入口到出口的路径, 因为如果出口结点 i 的 record[i] 值为-1 则表明遍历过程没有找到出口,也就是说此迷宫无解. 7. 反之 record[i]!= -1,则此迷宫一定是有解的,因为只有遍历过程中找到了出口 I,才会改变 record[i]的值,而这个改变后的值是不可能为-1 的; 8. 输出从入口到出口的路径,用回溯法,只需将图中结点的编号换算成数组 maze 的坐标 即可。

三、详细设计

1. do{

基本过程的算法:设定 a[0][0]为入口位置;

若当前位置可通, 则{将当前位置插入栈顶; 若该位置是出口位置,则结束; 否则切换当前位置的东邻方块为新的当前位置; } 否则, 若栈不空且栈顶位置尚有其他方向未经探索,

则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块; 若栈不空但栈顶位置的四周均不可通, 则{删栈顶位置; 若栈不空,则重新测试新的栈顶位置, 直到找到一个可通的相邻块或出栈至栈空; } }while(栈不空) ;#include <malloc.h>

2. 函数的调用关系图 迷宫存储从 A[0][0]开始,包括记录路径的数组 record[]也是从 0 下标开始纪录的,为了使输入 和输出的坐标符合习惯,只在输入输出时作了一些改变。 迷宫主要部分转换图示矩阵转化成图的邻接表存储: [i](G.vexs[i].data,G.vexs[i].first)→(adjno,next) [1] (0,first)→(11,NULL) [2] (1,NULL) [3] (1,NULL) ?? [11](0,first)→(21,next)→(1,NULL) ?? [59](0,first)→(60,next)→(49,NULL) [60](0,first)→(59,NULL) 以入口结点作广度优先遍历的起始结点,知道找到出口结点结束遍历,并用 record[i]记录遍 历的结点 i 的前驱结点 record[i],然后用回溯法输出路径(路径换算成坐标形式)即可。

3.抽象数据类型定义描述 ① ADT T is Data 当前位置的行坐标、当前位置的列坐标、走到下一位置的方向 end ADT T ② ADT Linknode is Data 数据域、指针域 Operation Linknode //构造函数

用于构造结点 end ADT LinkNode ③ ADT Stack is Data 栈顶指针 Operation Stack 输入:无 初始化栈:置空栈 ~stack Push //析构函数 //构造函数

输入:要进栈的项 e 前置条件:无 动作:把 e 压入栈顶 输出:无 后置条件:栈顶增加了一个新结点,栈顶指针指向新结点 Pop 输入:无 前置条件:栈非空 动作:弹出栈顶元素 输出:返回栈顶元素的值 后置条件:删除栈顶元素 GetPop 动作:返回栈顶元素的值 Clear 动作:清空栈 empty 动作: 检查栈顶指示是否等于 NULL 输出:栈空时返回 1,否则返回 0 end ADT Stack

四、调试分析

1)程序将用到的函数及参数: 1. 2. 3. 4. 迷宫输入: adjlist input (int maze [][MAX]); 迷宫图的图结构(邻接表存储)化: adjlist convert (int maze [][MAX],adjlist G); 对图的广度优先遍历: void travgraph(adjlist G,int record[],int entry,int exit); 迷宫的解的输出: void output (adjlist G,int record[],int entry,int exit)。

2)算法分析和改进 在程序的设计中,总的调试比较顺利。在找出一些小问题顺利编译成功以后,在测试结果的 时候发现程序运行的结果错误。 经过仔细的检查, 发现程序中 8 个 if 语句中的算法出现错误。 导致运行时搜索的方向发生错误。在 if 语句中的”i-1<G.colnum&&j+1<G.colnum”转换为” i-1>=0&&j+1<G.colnum”后,错误解除。经过测试结果,结果正确。 虽然程序能够编译成功,但是还有 2 个警告项存在.winTC 提示警告: success.c 126 :不可移动的指针(地址常数)转换在 travgraph 函数中。 success.c 132 :不可移动的指针(地址常数)转换在 travgraph 函数中。 经过改进,问题成功解决。警告消失。对于不能显示汉语的 TC,最后将中文转换为英 文,唯一不足的是(*,*) 在显示的时候是乱码。未能几时改进。

3)体会: 要能很好的掌握编程,仅仅通过几个简单的程序的编写是无法达成的,更需要大量 积累和 深入才有可能。就从这个迷宫的问题来说,在迷宫图向图结构的转化时,对图可用广度优先 搜索的算法来解决两点间路径问题。在程序的编写中也不能一味得向已有的程序进行模仿, 而要自己去摸索,去寻求最好的解决方式,只有带着问题去反复进行实践,才能更熟练的掌 握和运用,当然,对现有的程序也要多去接触,因为有些程序是我们无法在短时间内想出来 的。最重要的一点就是要持之以恒,要经常性的复习原来所接触的程序,这样才能保证我们 有足够的经验去面对程序问题。

五、测试结果:

1.运行出现“Please input the length of the maze” 字样, “rownum” 表示输入” 行数”“colnum” 表示输入”列数” 。 2.然后会出现 “Input the 1 row” 这时输入数组的第一行,后面的依次类推。 3.数组输入完毕后,会出现” Inputting the maze entrance sits the mark(*,*) ” 即输入起点坐标。 然后会出现”Inputting the maze exports to sit the mark(*,*) ” 要求输入出口坐标。 4.点击回车运行 所求的路径即会显示出来。

所示输入迷宫大小: 行数(<=15) :10 [↙] 列数(<=15) :15[↙] 0 表示可通行,1 表示不能通过。 输入第 1 行:[1] 输入第 2 行:[2] 输入第 3 行:[3] 输入第 4 行:[4] 输入第 5 行:[5] 输入第 6 行:[6] 输入第 7 行:[7] 输入第 8 行:[8] 输入第 9 行:[9] 输入第 10 行:[10] 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 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 1 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0

输入入口坐标(*,*) :1,1 输入出口坐标(*,*) :10,15

附录

1.存储结构:邻接表存储存储 2.基本过程的算法: (1). 栈初始化; (2). 将入口点坐标及到达该点的方向(设为-1)入栈; (3). while(栈不空时) { 栈顶元素元素(x,y,d)出栈; 求出下一个要试探的方向 d++; while (还有剩余试探方向时) { if(d 方向可走) 则{ (x,y,d)入栈; 求新点坐标(i,j) ; 将新点(i,j)切换为当前点(x,y) ; if ( (x,y)= = (n,n) )结束; else d=0; } else d++; }

}

3.源程序:

#include <stdio.h> #define MAX 15 #define NULL 0

typedef struct listnode {int adjno; struct listnode *next; }listnode;

typedef struct {int data; listnode *first; }headnode;

typedef struct {headnode vexs[MAX*MAX]; int vexnum;

int rownum; int colnum; }adjlist; adjlist G;

/*输入迷宫,0 为可通行,1 为不可通行,用二维矩阵表示*/

adjlist input (int maze[][MAX],adjlist G) {int i,j; int rownum,colnum; printf("Please input the length of the maze:\n"); printf("rownum="); scanf("%d",&G.rownum); printf("colnum="); scanf("%d",&G.colnum); for(i=0;i<G.rownum;i++) {printf("Input the %d row:[%d] ",i+1,i+1); for(j=0;j<G.colnum;j++) scanf("%d",&maze[i][j]); } return(G);

}

/*二维数组向无向图的转化*/ adjlist change (int maze[][MAX],adjlist G) {int i,j; listnode *p; G.vexnum=G.rownum*G.colnum; for(i=0;i<G.vexnum;i++) /*图中结点的初始化*/

{G.vexs[i].data=maze[i/G.colnum][i%G.colnum]; G.vexs[i].first=NULL; } for(i=0;i<G.rownum;i++) for(j=0;j<G.colnum;j++) {if(i-1>=0&&maze[i-1][j]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i-1)*G.colnum+j; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(i+1<G.rownum&&maze[i+1][j]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i+1)*G.colnum+j; /*将无向边用指针表示出来*/

p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(j-1>=0&&maze[i][j-1]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=i*G.colnum+j-1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(j+1<G.colnum&&maze[i][j+1]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=i*G.colnum+j+1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(i-1>=0&&j-1>=0&&maze[i-1][j-1]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i-1)*G.colnum+j-1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(i-1>=0&&j+1<G.colnum&&maze[i-1][j+1]==0)

{p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i-1)*G.colnum+j+1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(i+1<G.colnum&&j-1>=0&&maze[i+1][j-1]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i+1)*G.colnum+j-1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } if(i+1<G.colnum&&j+1<G.colnum&&maze[i+1][j+1]==0) {p=(listnode *)malloc(sizeof(listnode)); p->adjno=(i+1)*G.colnum+j+1; p->next=G.vexs[i*G.colnum+j].first; G.vexs[i*G.colnum+j].first=p; } } return(G); }

/* 用 int travgraph()函数广度优先遍历无向图*/

int travgraph(adjlist G,int record[],int entry,int exit) {listnode *p; int queue[MAX*MAX],visited[MAX*MAX]; /*用 visited[]数组标记图的结点是否遍历过*/ int i; int front=0,rear=1; for(i=0;i<G.rownum*G.colnum;i++) {record[i]=-1;/*置 record[i]为-1,以便检查从入口到出口结点 V[n]有无通路*/ visited[i]=0; } visited[entry]=1; queue[rear]=entry; while(front!=rear) /*记录遍历路径, (record[i],i)表示存在从结点 record[i]到 i 的边*/

{p=G.vexs[queue[front+1]].first; while(p!=NULL) {if(visited[p->adjno]==0) {visited[p->adjno]=1; record[p->adjno]=queue[front+1]; queue[++rear]=p->adjno; if(p->adjno==exit) goto end; } p=p->next;

} front=front+1; } end:; }

/*用回溯法找到从出口到入口的路径,并输出*/ void output (int record[],int entry,int exit) {int i=0,t; if(entry==exit&&G.vexs[exit].data==0) printf("It's already at export\n"); else if(record[exit]!=-1) {t=exit; {printf("The most short path is as follows:\n"); while(t!=entry) {printf("[%d,%d]<-",t/G.colnum+1,t%G.colnum+1); t=record[t]; if(++i%5==0)printf("\n"); } printf("[%d,%d]",t/G.colnum+1,t%G.colnum+1); }

} else printf("Have no path from the entrance to the exit\n"); }

void main() {int entry_row,entry_col,exit_row,exit_col,entry,exit; int maze[MAX][MAX]; int record[MAX*MAX]; G=input(maze,G); G=change(maze,G); printf("Inputting the maze entrance sits the mark(*,*) :"); scanf("%d,%d",&entry_row,&entry_col); printf("Inputting the maze exports to sit the mark(*,*) :"); scanf("%d,%d",&exit_row,&exit_col); entry=--entry_row*G.colnum+--entry_col; exit=--exit_row*G.colnum+--exit_col; travgraph(G,record,entry,exit); output(record,entry,exit); getch(); }

4.测试数据和结果

输入: 行数(<=15) :10 [↙] 列数(<=15) :15[↙] 0 表示可通行,1 表示不能通过。 输入第 1 行:[1] 输入第 2 行:[2] 输入第 3 行:[3] 输入第 4 行:[4] 输入第 5 行:[5] 输入第 6 行:[6] 输入第 7 行:[7] 输入第 8 行:[8] 输入第 9 行:[9] 输入第 10 行:[10] 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 0 1 0

输入入口坐标(*,*) :1,1 输入出口坐标(*,*) :10,15

结果: The path is as follow: [10,15]<-[9,14]<-[8,15]<-[7,14]<-[6,13]<-[5,12]<-[4,11]<-[3,10]<-[3,9]<-[4,8]<-[3,7]<-[2,7]<-[1,6]<-

[1,5]<-[2,4]<-[2,3]<-[1,1]

如图: 图 1-1 如上图:1.点击 success.exe 出现 “Please input the length of the maze”的字样 “rownum”表示输入”行数” “colnum”表示输入”列数” 2.然后会出现 “Input the 1 row” 这时输入数组的第一行,后面的依次类推 3.数组输入完毕后,会出现”Inputting the maze entrance sits the mark(*,*) ” 即输入起点坐标。 然后会出现”Inputting the maze exports to sit the mark(*,*) ” 要求输入出口坐标。 4.点击回车运行 所求的路径即会显示出来。

5.算法的改进方法: (*,*) 在显示的时候是乱码.应该改进。


相关文章:
编程题迷宫求解.doc
编程题迷宫求解 - 迷宫求解问题 摘要:用矩阵表示迷宫,将矩阵表示的迷宫转换成无
数据结构编程《迷宫问题》_图文.ppt
数据结构编程《迷宫问题》 - 迷宫问题 迷宫问题 主要内容 1.问题分析 2.递归算法 3.非递归算法 1.问题分析 o 1.问题分析 迷宫求解 这是一个找出口的问题。...
c语言实现 迷宫问题.doc
迷宫有一个入口,一 个出口。设计程序求解迷宫的一条通路。 2.数据结构设计以...根据题目中的数据,设置一个数组 mg 如下 int mg[M+2][N+2]= { {1,1...
迷宫求解问题分析(C语言)_图文.ppt
比如算法领域的经典问 题迷宫求解。在一个M×N的迷宫中, 给定一个入口,...21.2.2 问题实现本小节就来通过编程求解迷宫问题,实现的 代码如下。 1. ...
c语言实现 迷宫问题..doc
迷宫有一个入口,一 个出口。设计程序求解迷宫的一条通路。 2.数据结构设计以...根据题目中的数据,设置一个数组 mg 如下 int mg[M+2][N+2]= { {1,1...
迷宫求解课程设计(含引言、需求分析、伪代码、数据结构....doc
再或者没有通路时整个程 序结束,并输出迷宫无解的...另外的,菜单操作( 进行循环,否则循环结束程序结束。...《 数据结构习题 》李春保 清华大学出版社 《 数据...
走迷宫问题以及C++程序代码.doc
迷宫 M*n 格的迷宫,1 表示可以走,0 表示不可以走 读入:m*n 个数据和...二级C上机编程题思路及其... 4页 免费 喜欢此文档的还喜欢 走迷宫程序(c++...
走迷宫问题以及C 程序代码.pdf
顺序表C语言的程序代码 5页 5下载券 二级C上机编程题思路及其... 4页 免费...迷宫(C语言版) 7页 免费 迷宫求解数据结构课程设... 16页 1下载券 ...
北邮数据结构实验-题目三迷宫求解.doc
北邮数据结构实验-题目迷宫求解_计算机软件及应用_IT/计算机_专业资料。北邮数据...程序分析 2.1 存储结构存储结构:顺序栈 data data data top A3 A2 top (1...
迷宫问题求解.doc
迷宫问题求解 - 数据结构实验报告 实验名称: 实验 2题目 3 学生姓名:
迷宫问题求解最新版(新增DIY流程图).doc
迷宫问题求解最新版(新增DIY流程图)_计算机软件及应用_IT/计算机_专业资料。自己...这么难的题目我们怎么会啊, 但我们只能尽我们自己最大的努力把程序给写出来, ...
迷宫问题的C,C++算法实现.doc
求解迷宫问题,即找出从入口到 出口的路径。 一个迷宫可用上图所示方阵[m,n]...迷宫的生成 根据题目的要求,迷宫的大小是自定义输入的。所以在程序中用 malloc ...
迷宫问题实验报告(c++编写,附源代码).doc
迷宫问题实验报告级 班年月日 姓名 学号_ 1.实验题目 以一个 mXn 的长方阵表示迷宫,0 和 1 分别表示迷宫中的通路和障碍。设计一个程序, 对任意设定的迷宫,...
迷宫程序设计.doc
迷宫程序设计_工学_高等教育_教育专区。数据结构 (一)设计题目:迷宫 设计题目:...{ //求解迷宫 M 中,从 Start 到 end 的一条路径 //若存在则返回 true,...
迷宫问题的C,C 算法实现汇总.doc
下图是一个迷宫的 示意图: 二. 算法基本思想迷宫求解问题是栈的一个典型应用...迷宫的生成 根据题目的要求,迷宫的大小是自定义输入的。所以在程序中用 malloc ...
数据结构 迷宫问题求解.doc
(2)能针对给定题目,选择相应的数据结构,分析并设计算法, 进而给出问题的正确...1)首先实现一个以链表作存储结构的栈类型,然后编写一 个求解迷宫的非递归程序...
c语言课程设计作业迷宫问题求解哈希表查找的设计.doc
执行文件为:迷宫问题求解.exe 2、进入演示程序后即显示 DOS 形式的界面: 3、输入迷宫布局。系统会自动给出路径。 测试结果 二设计题目哈希表查找的设计 任务设...
迷宫问题c++实验报告.doc
迷宫由m行n列的二维数组设置,0表示无障碍,1表示有障碍。设入口为(1,1),出口为(m,n),每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现...
数据结构课程设计迷宫问题求解.doc
数据结构课程设计迷宫问题求解 - 扬州大学信息工程学院 《数据结构》 ---课程设计报告 题目: 班级: 学号: 姓名: 迷宫问题 计科 1301 131404126 张艳 指导教师:...
数据结构课程设计--求解迷宫问题.doc
数据结构课程设计--求解迷宫问题 - 课程设计(论文) 题目名称课程名称学生姓名学系 、专号业 信息工程系、电气信息类(信息类) 申寿云 迷宫求解 数据结构课程设计...