合肥学院。
计算机科学与技术系。
2011 ～2012 学年第二学期。
2012 年 6月13日。
一．题目：佳佳在一个实验室工作，他每天晚上都要一个人工作到很晚很晚，即使他再努力，也不能避免要上厕所的命运。佳佳是个胆小的孩子，黑夜里上厕所却是一件需要胆量的事，所以佳佳想让你帮他计算一下去厕所的路。
实验室所在的大楼的地形是一个n*n的正方形，每个点或者有路，或者是墙。 这里有一些地方是比较可怕的（比如会有呜呜的风声，或者那里没有灯光），每一个这种地方有一个可怕值k，佳佳经过这里的时候会在心里留下k的阴影。佳佳有一个心理承受能力s，当累计的k值超过或等于s时，佳佳会落荒而逃奔回实验室……现在请你帮佳佳看看，他能不能安全到达厕所呢？
实验室在地图的左上角，而厕所在地图的右下角。
设计程序完成如下要求：
1）输入：多组测试数据；每组数据输入的第一行是两个数n,s(n<=10,s<=10^9)；接下来n行，每行有n个数，分别代表：0 这个位置是空地（实验室和厕所都是0），-1 这个位置是墙，其他正整数：
这个位置的可怕程度。
2）输出：对于每组数据，输出yes表示佳佳能安全到达厕所，否则输出no。
3）所设计的数据结构应尽可能节省存储空间。
4）程序的运行时间应尽可能少。
二．问题分析：
根据题目要求我们可以将阴风习习的大楼问题（佳佳上厕所问题）抽象为如下一个查找矩阵中左上角到右下角带权最短路径模型。
图1把大楼抽象成上图所示的**形状，若坐标设为（1,1）~（n,n），这样实验室的坐标就是（1,1），而厕所的坐标就是（n,n）。图中每个单元格中的数代表这一点的恐怖值，-1代表这点是墙，不可通过。通过这样的抽象，我们的任务就是完成计算从左上角（1,1）开始遍历到达右下角（n,n）的最短带权路径长度。
实现模型的要求需要解决一下一个问题：
1. 怎样存储这个模型，即模型的数据结构。
2. 怎样对模型进行遍历，每一点邻接位置有4个。
3. 怎样判断当前遍历到终点的路径是最小的带权路径。
4. 怎样解决每个点访问权限的问题。即一个路径对每个点只能访问一次，一个点可以被多个路径访问。
5. 判断找到的最短路径与心理承受值大小。
本程序的关键问题和难点在于如何遍历找出带权最短路径。
如上图1，建立如下坐标系：
图2这样我们的目标就是计算出从（0,0）到达（5,5）点的最短路程。当然我们大可不必计算出最短的，因为要求只需要判断是否有权值和小于等于心理承受能力的一个路径。但我们能找出最短路径也就可以稍加修改的完成程序要求了。
除了边上和顶角的点，每个点向后都有四个选择，去掉来到该点的一个选择，还有三个选择；边上的点有两个选择；顶角的只有一种选择。为了避免边角的判断，我们可以将**扩大一点。这在详细设计中具体介绍。
从（0,0）点开始我们优先选择下边的邻接位置，次之访问右边的邻接位置。当到达下边的（1,0）时，用相同大小的数组记录到这个路径当前位置到达起点的累积权值，比如（0,1）记录为5 ，因为（1,0）为墙，不记录在内。然后是（1,1）……直到找到终点（5,5）或是路径是死路，就返回到上个位置，并查找上个位置的其他邻接位置。
也就是深度优先搜索遍历。
这样当我们走完所以起点到终点的路径后，终点位置就记录了最短路径的权值了。
三．概要设计和数据结构选择。
1.上面用一个二维矩阵来表示大楼情况，所以现在就定义以下数据结构来存储矩阵：
struct go_to_stool
int n大楼的边长。
long int s佳佳的心理承受能力。
long int building[maxlen+2][maxlen+2大楼的存储结构。
2.同时为了记录访问路径中个点的访问情况和路径累积权值，还需要定义如下的数据结构来存储：
struct visite访问标志结构。
int swap[maxlen+2][maxlen+2]; 是否交换过标志。
int tag[maxlen+2][maxlen+2]; 访问标志。
long int visited[maxlen][maxlen存放各点到终点的最短路径。
3.流程图。调用完。n
y图3四．算法思想。
程序的核心是遍历这个二维矩阵，得到带权的最短路径，主要算法思想如下：
1. 采用递归的深度优先搜索遍历路径。
2. 首先遍历一个点的下侧邻接点，然后遍历其右侧邻接点，其次是左侧，再者是上侧。
3. 每个邻接点有四个属性：a.
该点的权值，即大楼该位置的恐怖值或墙。b.该点的访问标志。
c.该点到起点的累积最小权值。d.
该点权值交换标志。
4. 从左上角的起点（0,0）开始深度优先遍历，每次遍历到一个点时判断该点是否为墙并且没有被访问过，然后判断该点的累积权值是否被交换过，若没有则将该路径上一个点的累积权值加上该点的权值作为该点的累积权值，这样就记录了该点到起点的累积路径权值了。这样遍历到终点就会记录该路径上个点到起点的累积权值，不过这不一定是最小的。
根据递归函数的性质，将退回上个节点遍历其他路径，这样，当一个点被重复遍历到时则将该点的累积权值交换为最小路径的累积权值。这样当遍历完所有路径后，就记录了每个点到达起点的最小路径权值了。我们想要的终点到起点的最小路径权值和也就出来了。
同时也知道了最短路径。
图4如图4，是一条路径遍历的结果，遍历到终点时便记录了这条路径的带权长度。
五。详细设计。
1. 定义大楼类型和访问存储类型：
struct go_to_stool //大楼类型。
int n大楼的边长。
long int s佳佳的心理承受能力。
long int building[maxlen+2][maxlen+2大楼的存储结构。
struct visite访问标志结构。
int swap[maxlen+2][maxlen+2]; 是否交换过标志。
int tag[maxlen+2][maxlen+2]; 访问标志。
long int visited[maxlen][maxlen存放各点到终点的最短路径。
将存储大楼数据的数组扩大一圈可以解决需要考虑边缘位置只有2或1邻接位置，简化计算。
2． 初始化大楼属性和输入大楼的属性数据。
for(i=0;i for(j=0;jw->building[i][j]=-1;
采用两个for循环，将大楼的结构初始化为墙，避免后面访问时出现未知数据的情况。这一个初始化将外围全部赋值为-1，即是墙，这样在访问边位置的时候就方便了。
for(i=1;i<=w->n;i++)
for(j=1;j<=w->n;j++)
scanf("%ld",&w->building[i][j]);得到大楼结构。
同样采用两个for循环的结构，输入大楼的数据，注意这里i从1开始，到给定的一个边长结束，这个边长最大为10，而我们定义的数据结构给出最大为12，这样这个二维数组的第0行，第0列，第maxlen+1行，第maxlen+1列都初始化为墙了。后面访问时就可以把所有点的邻接位置归结为3种了。
2. 遍历算法举例说明。
为了简化问题说明，我们用一个4*4的矩阵来表示大楼的结构，即大楼边长为4。
图5a. 递归函数简介：
首先介绍下程序的核心递归函数，方便后面举例讲解。 这个递归函数是从起点开始（程序需要也可以从任何点开始）深度优先递归访问它的下邻接位置，其次递归访问右邻接位置，再者是上，最后是左邻接位置。访问需要一定条件，必须访问到的位置不能是墙，无已访问标志。
函数中用到4个数组，一个是building用于存储大楼结构的，一个人tag用于标志某个点是否访问过。一个是swap用于标志visited中累积权值是否被交换过，一个是visited用于记录各点到起点的权值累积。
b．如图5，边缘为的-1都是初始化为墙的。首先从起点（1,1）开始访问，（1,1）有四个邻接位置但是其中有2个是墙，则（1,1）点有两种走法，首先走下面。
if(w->building[i+1][j]!=1 &&v->tag[i+1][j]!=1 &&v->swap[i+1][j]!=1)
通过if语句判断它的下邻接位置是否是墙、有没有被访问过、有没有交换记录。如都是否，则v->visited[i+1][j]=v->visited[i][j]+w->building[i+1][j];
记录下下邻接位置的累积权值，然后标记为访问过、交换过：v->tag[i+1][j]=1;v->swap[i+1][j]=1;然后递归的访问（2,1）的下邻接位置。同上面判断它的邻接位置（3,1）是墙，这结束该次访问，即递归函数返回到上一次调用中；接着优先访问右邻接位置，即（2，2）。
这样递归的访问到终点后，终点就记录了本次路径的累积权值，但这不一定是最小的。根据递归函数性质，函数会返回到上一个位置，查找其它的邻接位置，形成其它路径。当其它路径经过和本路径同一点时，取最小的权值累积。
v->visited[i-1][j]=min(v->visited[i-1][j],v->visited[i][j]+w->building[i-1][j]);
当递归函数完成以后，所有可能到达的路径就都遍历过了，这样各点就都记录下到达起点的最短距离了。
图6如上图，当递归函数结束后，我们可以看到终点就保存着最小的累积权值。这样我们从终点开始向起点走，每步选择最小的权值累积的位置走，就可以得到最短路径了。
六．上机调试。
1. 语法错误及修改：由于本算法使用了递归的思想进行遍历，所以程序可以相对来说得到了简化，语句有所减少。
所以出现的语法问题主要在于子函数和变量的定义，括号的配对，关键字和函数名称的书写，以及一些库函数的规范使用。这些问题均可以根据编译器的警告提示，对应的将其解决。
课程设计报告格式 课程设计
洛阳理工学院。课程设计说明书。课程名称。设计课题。专业。班级。学号。姓名。完成日期2014年12月26日。问题描述 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的内容要求。基本要求 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的基本要求。测试数据 小四宋体，行间距单倍行距，每...
课程设计总结,课程设计报告
课程设计总结，课程设计报告。3.尝试应用项目管理软件进行项目进程的规划管理 绘制甘特图，不作硬性要求 二 选题说明。人事管理是企业信息管理的重要部分，面对大量的人事工资信息，财务部门采用人力处理将浪费大量的时间 人力和物力，且数据的准确性低。因此，开发一个界面友好，易于操作的人事工资管理软件进行自动...
课程设计 课程设计报告格式
学校名。课程设计报告。课程名称 c语言程序设计 系别 专业班级 学号。姓名。课程题目 企业人事管理系统 完成日期 指导老师 年月日。附件。课程设计的内容。企业人事管理系统 本项目的目标是开发一个功能实用，操作简便，简单明了的人事管理系统。能够录入人事的基本资料，在操作上能够完成诸如添加 修改 删除 ...