#6 一起来学算法吧!
题目背景
没有背景
学习算法对于刚接触编程的小白来说也许难度会比较大,但在学习算法的过程中可以快速提高同学们的编程能力,并且培养良好的编程思维。
我们鼓励同学们使用搜索引擎来学习算法,但请不要直接将网上的题解直接复制提交,我们也将在后续的考核中判断大家是否真正理解了这些算法。同时比起题目的完成度,我们更关心大家的学习态度。
题目内容
任务一:搜索
大家一定都玩过走迷宫,现在我们可以通过编程来让计算机帮我们设计走出迷宫的方案和最短通关路径,只需要编写一个小程序就能将它应用在所有的迷宫上。
给定一个n*m大小的01方格迷宫,其中1表示障碍,0表示允许通行,在迷宫中有上下左右四种移动方式,每次只允许移动一个方格,并且每个方格只允许经过一次,给定起点坐标和终点坐标,问:从起点到终点有几条路径,同时求出最短路径的长度。数据保证起点和终点上不会有障碍,如果路径数为0,则最短路径长度也输出0。
输入格式:
第一行n,m表示迷宫大小。
第二行起点坐标Sx,Sy。
第三行终点坐标Fx,Fy。
接下来n行是表示迷宫的01矩阵。
(1≤n,m≤10,同一行中的不同数据用一个空格隔开)
输出格式:
第一行输出从起点坐标到终点坐标的路径总数,第二行输出最短路径的长度。(路径长度为经过的格子总数,起点也计入路径)
输入样例:
3 3
1 1
2 3
0 1 1
0 0 0
1 0 0
输出样例:
2
4
参考资料:
google,百度
提示:
1.迷宫问题一般采用深度优先搜索和广度优先搜索两种方法。
3.(加分项)有能力的同学可以分别使用深度优先搜索和广度优先搜索编写两个程序提交。
任务二:动态规划
萌新劝退预警!!!
今年的中秋计划被暴雨冲毁了,zfy被迫留守在寝室中,百无聊赖之际zfy开发了一种兔子棋,给定一个n格直线棋盘,每一个格子上写着一个非负的整数表示在这个格子上的萝卜数量,第一格为起点,第n格为终点,玩家可以通过使用跳跃卡片来控制兔子从起点逐步跳到终点。
跳跃卡片共有m张,跳跃卡片共有四种(给定的m张跳跃卡片中不一定包含所有的四种卡片),每种卡片上分别标有1,2,3,4四个数字之一,使用这种卡片后,兔子将向前跳跃相应的格子数。游戏中,玩家每次需要从所有的跳跃卡片中选择一张之前没有使用过的跳跃卡片,控制兔子跳跃前进相应的格子数。
游戏中,兔子自动获得起点格子的萝卜,并且在后续的跳跃过程中每到达一个格子,就得到该格子相应的萝卜。兔子最终得到的萝卜数量就是兔子从起点到终点过程中到过的所有格子的萝卜总和。
可以看出,不同的卡片使用顺序会影响最终兔子得到的萝卜总数,现在,告诉你棋盘上每个格子上的萝卜数量和所有的跳跃卡片,你能计算出兔子最多能得到的萝卜数量吗?
时间限制:1.00s 空间限制:125.00MB
输入格式:
第一行两个正整数n,m表示棋盘长度和跳跃卡片总数。
第二行n个非负整数 A1,A2,…,An,其中Ai表示第i个格子上的萝卜数量。
第三行m个整数,B1,B2,…,Bm,分别表示m张跳跃卡片上的数字。
同一行中的不同数据用一个空格隔开。
(1≤n≤350,1≤m≤120,0≤Ai≤100,1≤Bi≤4,并且对于四种跳跃卡片,每种跳跃卡片的张数不会超过40)
输出格式:
一个整数表示兔子最多能得到的萝卜数量。
输入样例:
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
输出样例:
73
参考资料:
google,百度
提示:
1.样例中跳跃卡片的使用顺序为1,1,3,1,2,最终得到的萝卜数6+10+14+8+18+17=73。
2.本题难度较大,对于新手不作要求。
3.当所有跳跃卡片用完时,兔子恰好能跳跃到终点。
4.即使没有完成这一题,也可以提交文档来记录你的学习过程和想法。(有加分)
说明:
1.建议同学们在编程的过程中能够在关键代码部分加上注释记录代码功能,以便我们理解你的代码,同时这也是一种良好的编程习惯。
2.请同学们用C/C++编写,任务一和任务二各有10个测试点,按照过的测试点数量给分。写完将源代码发到招新邮箱,同时如果有题解思路/学习过程文档将作为加分项。
3.请同学们不要尝试抄他人题解,独立完成,这将有利于之后的代码细节问答环节。