武汉理工大学基础强化报告ACM迷宫问题.docx
《武汉理工大学基础强化报告ACM迷宫问题.docx》由会员分享，可在线阅读，更多相关《武汉理工大学基础强化报告ACM迷宫问题.docx（12页珍藏版）》请在冰点文库上搜索。
武汉理工大学基础强化报告ACM迷宫问题
学号：
课程设计
（基础强化训练）
题目
迷宫问题
学院
计算机科学与技术学院
专业
软件工程
班级
姓名
指导教师
鄢红国
2014
年
7
月
12
日
课程设计任务书
学生姓名：
专业班级：
指导教师：
鄢红国工作单位：
计算机科学与技术学院
题目:
迷宫问题
初始条件：
输入：
一个5×5的二维数组，表示一个迷宫。
数据保证有唯一解。
输出：
左上角到右下角的最短路径。
要求完成的主要任务:
（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1、完成算法分析；
2、给出对应的程序流程图；
3、给出能正确实现的程序源码；
5、给出试算截屏图；
6、课程设计工作的分析与总结；
7、给出不少于5篇参考文献。
时间安排：
2014-7-6到2014-7-12
消化资料、系统调查、形式描述1天
系统分析、总体设计、实施计划3天
撰写课程设计报告书1天
指导教师签名：
2014年7月日
系主任（或责任教师）签名：
2013年7月日
目录
1注册资料3
2选题描述3
3算法分析4
3.1主函数调用各个模块4
3.2递归探索和最短路径的保存.......................................................................5
4程序流程图6
5程序源码7
6试算截屏图及代码通过图8
7分析与总结9
8参考文献9
附：
评分表....................................................................................................................10
迷宫问题
1注册资料
用户名：
214165
密码：
guanqing12@
选题题号：
3984
2选题描述
定义一个二维数组：
intmaze[5][5]={
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入：
一个5×5的二维数组，表示一个迷宫。
数据保证有唯一解。
输出：
左上角到右下角的最短路径，格式如样例所示。
样例输入：
01000
01010
00000
01110
00010
样例输出：
（0,0）
（1,0）
（2,0）
（2,1）
（2,2）
（2,3）
（2,4）
（3,4）
（4,4）
3算法分析
3.1主函数调用各个模块
迷宫问题分为创建迷宫，探索最短路径，最后输出最短路径三个主要模块，为了便于模块化管理，将这三部分分别编写代码，最后通过主函数调用。
主函数代码如下：
intmain（）
{
inti,j;
minn=25;
memset（b,0,sizeof（b））;//初始化数组置为0
memset（c,0,sizeof（c））;
for（i=0;i<5;i++）
for（j=0;j<5;j++）
scanf（"%d",&a[i][j]）;;
b[4][4]=1;
tyr（0,0,1）;
display（）;
return0;
}
3.2递归探索和最短路径的保存
解决迷宫问题的重点是探索最短路径，算法有很多种，我选择的是递归算法，定义了一个moves二维数组和变量i，j相加，这样可以保证探索路径的时候是往四个方向探索。
每次递归都利用change函数，将最短路径记录，递归结束后将最短路径保存在数组c中，最后调用display函数输出数组c，即结果。
voidtyr（inti,intj,intcount）
{//count用来记录递归的次数，并与最小值比较
//i,j为坐标数
intk;
if（i==4&&j==4）
{
if（count{
minn=count;
change（）;
}
return;//一次递归完成
}
for（k=0;k<4;k++）//用来做循环变量
{
intx=i+moves[k][0];
inty=j+moves[k][1];//保证往各个方向移
if（x>=0&&x<5&&y>=0&&y<5&&a[x][y]==0）
{//x，y坐标不越界
b[i][j]=1;
a[i][j]=1;
count++;
tyr（x,y,count+1）;//又走了一步
count--;
b[i][j]=0;
a[i][j]=0;
}
}
}
voidchange（）
{
inti,j;
for（i=0;i<5;i++）
for（j=0;j<5;j++）
c[i][j]=b[i][j];
}
4程序流程图
图1：
程序流程图
5程序源码
#include
#include
inta[7][7],c[7][7],minn;
intb[5][5];
intmoves[4][2]={{0,-1},{-1,0},{0,1},{1,0}};/*显示*/
voiddisplay（）
{
inti,j;
for（i=0;i<5;i++）
for（j=0;j<5;j++）
if（c[i][j]==1）
printf（"（%d,%d）\n",i,j）;
}
/*用数组c保存最短路径*/
voidchange（）
{
inti,j;
for（i=0;i<5;i++）
for（j=0;j<5;j++）
c[i][j]=b[i][j];
}
/*递归搜索*/
voidtyr（inti,intj,intcount）
{//count用来记录递归的次数，并与最小值比较
//i,j为坐标数
intk;
if（i==4&&j==4）
{
if（count{
minn=count;
change（）;
}
return;//一次递归完成
}
for（k=0;k<4;k++）//用来做循环变量
{
intx=i+moves[k][0];
inty=j+moves[k][1];//保证往各个方向移
if（x>=0&&x<5&&y>=0&&y<5&&a[x][y]==0）
{//x，y坐标不越界
b[i][j]=1;
a[i][j]=1;
count++;
tyr（x,y,count+1）;//又走了一步
count--;
b[i][j]=0;
a[i][j]=0;
}
}
}
intmain（）
{
inti,j;
minn=25;
memset（b,0,sizeof（b））;//初始化数组置为0
memset（c,0,sizeof（c））;
for（i=0;i<5;i++）
for（j=0;j<5;j++）
scanf（"%d",&a[i][j]）;;
b[4][4]=1;
tyr（0,0,1）;
display（）;
return0;
}
6试算截屏图及代码通过图
图2：
程序VC++6.0试算运行图
图2：
北大ACM网站提交程序记录图
图3：
北大ACM网站程序通过截图
7分析与总结
对最短路径的探索，主要就是探索的方式的选择，我这次选择了代码比较简单的递归探索方式。
不同的探索方式对程序的效率有很大的影响，选择合适的算法往往比编写代码的过程更重要。
在探索完成之后对数据的保存也必须考虑。
虽然这次实验的代码不是很长，但是也要有注意模块化程序的思想，并且有必要的注释。
通过这次实验，我收获了很多，比如各种探索方式，在什么情况下效率更高，这跟上学期学习的数据结构课程有很大的关系。
当然我发现了自己很多的不足，比如之前过于注重学习各种编程语言，忽略了算法对一个程序的重要性。
在以后的编程学习中，我应该专注于一门编程语言，强化自己对代码效率的考虑，多多编程，提高自己对算法的思考和运用能力。
8参考文献
[1]李文新、郭炜、余华山.程序设计导引及在线实践[M].北京：
清华大学出版社
[2]谭浩强.C程序设计[M].北京：
清华大学出版社，2005.
[3]严蔚敏，吴伟民.数据结构[M].北京:
清华大学出版社，1996.
[4]钟珞.计算机科学导论[M].武汉：
武汉理工大学出版社.
[5]张蕊、吕涛.C程序设计教程.武汉：
华中科技大学出版社
升级会员 