爱奇艺笔试题——草原坝上滑梯
2、Description
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <=
100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
Sample Output
25
#include <iostream> #include <algorithm> using namespace std; int r;//行 int c;//列 int a[1000][100];//输入矩阵 int result[1000][1000];//输出矩阵 //递归思想：分别求出上下左右方向的最大长度 int maxLength(int i, int j) { int left = j - 1; int right = j + 1; int high = i - 1; int low = i + 1; int left_value; int right_value; int high_value; int low_value; //左侧最大长度 if (left >= 0 && a[i][left] < a[i][j]) left_value = maxLength(i, left) + 1; else left_value = 0; //右侧最大长度 if (right <= c - 1 && a[i][right] < a[i][j]) right_value = maxLength(i, right) + 1; else right_value = 0; //上侧最大长度 if (high >= 0 && a[high][j] < a[i][j]) high_value = maxLength(high, j) + 1; else high_value = 0; //下侧最大长度 if (low <= r - 1 && a[low][j] < a[i][j]) low_value = maxLength(low, j) + 1; else low_value = 0; int max1 = max(high_value, low_value); int max2 = max(left_value, right_value); return max(max1, max2); } int main() { while (cin >> r >> c) { //初始化矩阵 for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) cin >> a[i][j]; //计算每一个位置的最大长度 for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) result[i][j] = maxLength(i, j); //寻找所有位置中最大的长度 int maxLen = 0; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) if (result[i][j] > maxLen) maxLen = result[i][j]; } cout << maxLen + 1 << endl; } system("pause"); return 0; }
