|
#2
rjsp2017-04-27 11:11
 程序代码：#include <stdio.h> int main( void ) { for( unsigned w,h; scanf("%u%u",&w,&h)==2; ) { enum { B=1, U=2, D=4, L=8, R=16 }; // 障碍物、上、下、左、右 unsigned char m[10][10] = { 0 }; // 地图 // 读入地图 unsigned start_r=-1, start_c=-1; // 起点 unsigned direction; // 当前行走方向 unsigned count = 0; // 踏过的方格数量 for( unsigned r=0; r!=w; ++r ) for( unsigned c=0; c!=h; ++c ) { char ch; scanf( " %c", &ch ); switch( ch ) { case '.': m[r][c]=0; break; case '*': m[r][c]=B; break; case 'U': m[r][c]=0; start_r=r, start_c=c; direction=U; break; case 'D': m[r][c]=0; start_r=r, start_c=c; direction=D; break; case 'L': m[r][c]=0; start_r=r, start_c=c; direction=L; break; case 'R': m[r][c]=0; start_r=r, start_c=c; direction=R; break; } } // 遍历 for( ; start_r!=-1; ) { if( (m[start_r][start_c]&direction) != 0 ) // 之前以相同方向走过此格 break; if( (m[start_r][start_c]&(U|D|L|R)) == 0 ) // 之前未曾走过此格 ++count; m[start_r][start_c] |= direction; // next switch( direction ) { case U: if( start_r==0 || m[start_r-1][start_c]==B ) direction=R; else --start_r; break; case D: if( start_r==w-1 || m[start_r+1][start_c]==B ) direction=L; else ++start_r; break; case L: if( start_c==0 || m[start_r][start_c-1]==B ) direction=U; else --start_c; break; case R: if( start_c==h-1 || m[start_r][start_c+1]==B ) direction=D; else ++start_c; break; } } printf( "%u\n", count ); } return 0; } 授人以鱼，不如授人以渔，下面不写代码了，只是分析算法 题目 C（15 分） 行和列方法相同，以行为例： 每一行都有“挖”和“不挖”两种可能 如果是“挖”，那么其结果是 上上一行 的最大结果 + 本行最大结果 如果是“不挖”，那么其结果是 上一行 的最大结果 本行的结果是 “挖”和“不挖”两种情况下的最大值 举例（简化到每行只有一个数字） 第0行 4 第1行 1 第2行 2 第3行 5 第-2行，结果是0 第-1行，结果是0 第0行，结果是 max(0+4,0) = 4 第1行，结果是 max(0+1,4) = 4 第2行，结果是 max(4+2,4) = 6 第3行，结果是 max(4+5,6) = 9 题目 D（20 分） 从第一个数开始，比其尾部小的就加入到尾部，直到结束 重复上述过程，一共重复了几次就输出几次 （没看出有什么特殊的地方，分值反而比“题目 C”还高？！那或许是我想简单了） 题目 E（15 分） 效率低但胜在简单的方法是递归 unsigned foo( n, k ) { if( n == k ) return 0; return 1 + min( 如果k>=一个半的n有foo(2*n,k), 如果n>1有foo(n-1,k), 如果n<k有foo(n+1,k) ); } 假设一共乘车m次 n*2^m + a*2^A + b*2^B + c*2^C + …… = k （abs(a、b、c)==1） 还是蛮复杂的 |
几道中南大学考研机试题
哪位老哥大神能告诉我每道题考得什么算法
要是能求解，上代码就更好了。谢谢帮助
题目 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 分钟。