在C语言中:Michael喜欢滑雪这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子。 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更长。事实上,这是最长的一条。 输入描述: 输入的第一行表示区域的行数n和列数m(1<=n, m<=100)。下面是n行,每行有m个整数,代表高度h,0<=h<=10000。
时间: 2024-02-12 13:02:40 浏览: 104
这是一道经典的动态规划问题,可以使用递归或者动态规划来解决。
一种动态规划的思路是,定义一个二维数组dp,其中dp[i][j]表示从点(i,j)开始的最长滑坡长度。初始状态为dp[i][j]=1,因为从任何一个点开始,最长的滑坡长度至少为1。然后,从左到右,从上到下遍历数组,对于每个点(i,j),计算它能够滑行到的相邻点的dp值,取最大值加1作为dp[i][j]的值。最后,遍历整个dp数组,找到最大值即可。
具体实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
#define MAXM 100
int n, m;
int h[MAXN][MAXM], dp[MAXN][MAXM]; // h表示高度,dp表示最长滑坡长度
int max(int a, int b) {
return a > b ? a : b;
}
int solve() {
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = 1; // 初始状态为1
if (i > 0 && h[i-1][j] < h[i][j]) {
dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
}
if (j > 0 && h[i][j-1] < h[i][j]) {
dp[i][j] = max(dp[i][j], dp[i][j-1] + 1);
}
if (i < n-1 && h[i+1][j] < h[i][j]) {
dp[i][j] = max(dp[i][j], dp[i+1][j] + 1);
}
if (j < m-1 && h[i][j+1] < h[i][j]) {
dp[i][j] = max(dp[i][j], dp[i][j+1] + 1);
}
ans = max(ans, dp[i][j]); // 更新最大值
}
}
return ans;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &h[i][j]);
}
}
printf("%d\n", solve());
return 0;
}
```
输入样例:
```
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
```
输出样例:
```
25
```
阅读全文