illusionssss 2017-04-26 14:03 采纳率: 0%
浏览 2418

中南大学考研几道机试题

几道中南大学考研机试题
哪位老哥大神能告诉我每道题考得什么算法
要是能求解,上代码就更好了。谢谢帮助
题目 B(20 分)
问题描述:
有一个愚蠢的机器人走进了一个 w*h 的迷宫,迷宫里有空地和陷阱。它想要走遍每一个方格,但是它很笨,只会按照指令方向走。当下一步是边界或者是陷阱时,它会向右旋转 90 度。请问这个机器人最多可以经过多少个方格?

数据输入:
对于每组数据,第一行两个数 w 和 h,分别表示迷宫的行和列(1≤w,h≤10)
接下来 w 行,每行有 h 个字符用于描述这个迷宫。迷宫中的‘.’表示空地,即可以走的地方;‘*’表示陷阱,即不能走的地方;迷宫中有一个英文字母,表示机器人的出发点。字母只可能是‘U’、‘D’、‘L’、‘R’,分别表示机器人初始指令方向是向上、向下、向左、向右。

结果输出:
对于每组数据,输出一个整数,表示机器人一共经过了多少个方格

输入示例:
2 3
U..
.*.
4 4
R...
.**.
.**.
....

输出示例:
4
12

题目 C(15 分)
问题描述:
在一片 n*m 的土地上,每一块 1*1 的区域里都有一定数量的金子。这一天,你来到这里淘金。然而当地人告诉你,如果你要挖(x,y)区域的金子,那么你就不能挖(x-1,y)、(x+1,y)以及纵坐标为 y-1 和 y+1 的金子(也就是说你挖某一区域的金子,左边、右边、上一行、下一行的金子你都不被允许挖了)。那么问题来了,你最多能淘多少金?

数据输入:
对于每组数据,第一行两个数 n 和 m,分别表示土地的长度和宽度(1≤n,m≤200)
接下来 n 行,每行有 m 个数表示每个区域金子的数量,每个区域金子数量不超过 1000

结果输出:
对于每组数据,输出最多能得到的金子数量

输入示例:
4 6

11 0 7 5 13 9

78 4 81 6 22 4

1 40 9 34 16 10

11 22 0 33 39 6

输出示例:
242

题目 D(20 分)
问题描述:
巨人国的小学生放学了,老师要给小朋友们排队了。可是这个老师有强迫症,一定要让路队上的小朋友按身高从高到矮排序。小朋友们呢也很调皮,一旦老师给他排好了队就不愿意动了。这时候小朋友们一个一个从教室里出来了,每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友们排几条路队?

数据输入:
对于每组数据,第一行一个整数 n,表示小朋友的总数(1≤n≤10000)第二行 n 个整数,表示每个小朋友的身高,身高不超过 30000

结果输出:
对于每组数据,输出一个整数,表示最少的路队数

输入示例:
8

389 207 155 300 299 170 158 65

输出示例

2

样例解释:
最少要排两条路队,其中一种方案是:389-207-155-65 和 300-299-170-158

题目 E(15 分)
问题描述:
你收到通知被中南大学录取了,高兴地来到长沙。很快你就来到了麓山南路上,已知你的位置是 N,中南大学的位置是 K。为了去中南大学,你有两种移动方式:走路或者坐公交车。走路:你可以从位置 X 移动到 X+1 或者 X-1 搭公交:你可以从位置 X 移动到 2X;
每次走路和搭公交所需的时间都是一分钟,你现在想尽快到中南大学,所需的时间是多少呢?

数据输入:
对于每组数据,输入一行,分别是 N 和 K(1≤N,K≤100,000)

结果输出:
对于每组数据,输出一个整数,表示所需时间

输入示例:
5 17

输出示例:
4

样例解释:
其中的一种方案是:5-10-9-18-17 所需时间是 4 分钟。

  • 写回答

3条回答 默认 最新

  • JIAN_BOY_RISE 2017-05-02 04:23
    关注

    分别是前三道分别是广搜、深搜、动态规划,最后一道题目用深搜也可以做,也可以用动态规划做,恩,大概是这样子的

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题