几道中南大学考研机试题
哪位老哥大神能告诉我每道题考得什么算法
要是能求解，上代码就更好了。谢谢帮助
题目 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 分钟。
分别是前三道分别是广搜、深搜、动态规划，最后一道题目用深搜也可以做，也可以用动态规划做，恩，大概是这样子的
B题有死循环应该要特判
不问了，全AC了
B、C、D、E AC代码如下
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct status {
int i;
int j;
char direction;
int moves;
int turned; // turned without move, if move reset this state to 0
};
bool notValid(char c) {
return c == '*' || c == 'x';
}
char turn(char c) {
string s = "RDLUR";
return s[s.find(c)+1];
}
bool move(vector<vector<char>> &v, status* s, int M, int N) {
char direction = s->direction;
bool success = true;
int curi = s->i, curj = s->j;
// cout << curi << " " << curj << " " << direction << " !!!" << endl;
switch(direction) {
case('U'):
if(curi-1 < 0 || notValid(v[curi-1][curj])) {
if(s->turned > 3) {
return false;
}
else {
s->direction = turn(direction);
s->turned++;
}
}
else {
s->i = curi - 1;
s->moves++;
s->turned = 0;
v[curi][curj] = 'x'; // no turning back
}
break;
case('R'):
if(curj+1 >= N || notValid(v[curi][curj+1])) {
if(s->turned > 3) {
return false;
}
else {
s->direction = turn(direction);
s->turned++;
}
}
else {
s->j = curj + 1;
s->moves++;
s->turned = 0;
v[curi][curj] = 'x';
}
break;
case('D'):
if(curi+1 >= M || notValid(v[curi+1][curj])) {
if(s->turned > 3) {
return false;
}
else {
s->direction = turn(direction);
s->turned++;
}
}
else {
s->i = curi + 1;
s->moves++;
s->turned = 0;
v[curi][curj] = 'x';
}
break;
case('L'):
if(curj-1 < 0 || notValid(v[curi][curj-1])) {
if(s->turned > 3) {
return false;
}
else {
s->direction = turn(direction);
s->turned++;
}
}
else {
s->j = curj - 1;
s->moves++;
s->turned = 0;
v[curi][curj] = 'x';
}
break;
}
return success;
}
int main() {
string directions = "UDLR";
int M, N, startx, starty;
char direction;
vector<vector<char>> v;
char c;
while(cin >> M >> N) {
v.clear();
v.reserve(M);
for(int i=0; i<M; i++) {
v.push_back(vector<char>());
v[i].reserve(N);
for(int j=0; j<N; j++) {
cin >> c;
v[i].push_back(c);
if(directions.find(v[i][j]) != string::npos) {
startx = i;
starty = j;
direction = v[i][j];
}
}
}
status* s = new status{startx, starty, direction, 1, 0};
bool able = true; // still movin, help me get up
do {
able = move(v, s, M, N);
} while(able);
cout << s->moves << endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> v;
int n, x;
while(cin >> n) {
v.clear();
for(int i=0; i<n; i++) {
cin >> x;
bool flag = false;
for(int i=0; i<v.size(); i++) {
if(x <= v[i]) {
v[i] = x;
flag = true;
break;
}
}
if(!flag) {
v.push_back(x);
}
sort(v.begin(), v.end());
}
cout << v.size() << endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;
int main() {
int n, m;
double val;
vector<vector<int>> v;
while(cin >> n >> m) {
v.clear();
v.reserve(n);
for(int i=0; i<n; i++) {
v.push_back(vector<int>());
v[i].reserve(m);
for(int j=0; j<m; j++) {
cin >> val;
v[i].push_back(val);
}
}
vector<int> opt, lineSum, optLines;
for(auto line : v) {
opt.clear();
if(line.size() > 0) {
opt.push_back(line[0]);
}
if(line.size() > 1) {
opt.push_back(max(line[0], line[1]));
}
for(int i=2; i< line.size(); i++) {
opt.push_back(max(opt[i-1], opt[i-2]+line[i]));
}
lineSum.push_back(opt.back());
}
if(v.size() > 0) {
optLines.push_back(lineSum[0]);
}
if(v.size() > 1) {
optLines.push_back(max(lineSum[0], lineSum[1]));
}
for(int i=2; i<lineSum.size(); i++) {
optLines.push_back(max(optLines[i-1],lineSum[i]+optLines[i-2]));
}
cout << optLines.back() << endl;
lineSum.clear();
optLines.clear();
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <set>
#include <queue>
#define LARGE 200001
using namespace std;
int arr[LARGE];
int main() {
int n, k;
while(cin >> n >> k) {
arr[n] = 0;
set<int> s;
s.emplace(n);
queue<int> q;
q.push(n);
while(!q.empty()) {
n = q.front();
if(n==k) {
cout << arr[k] << endl;
break;
}
q.pop();
if(n<k+1) {
if(s.emplace(n*2).second) {
arr[n*2] = arr[n] + 1;
q.push(n*2);
}
}
if(s.emplace(n+1).second) {
arr[n+1] = arr[n] + 1;
q.push(n+1);
}
if(n>0) {
if(s.emplace(n-1).second) {
arr[n-1] = arr[n] + 1;
q.push(n-1);
}
}
}
q = queue<int>();
s.clear();
}
return 0;
}