2、草原坝上滑梯
只能从上下左右侧移动
输入:行数R 列数C
输出:最长区域的长度
样例:
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
输出: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;
}