Description
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更长。事实上,这是最长的一条。
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
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更长。事实上,这是最长的一条。
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
// SkiProgram.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <stdio.h> using namespace std; //全局变量 int map[100][100] = { -1 };//输入数组 int path[100][100] = { -1 };//记录每个点的最长路径 int maxResult = -1; //记录最大值 int rows, cols; //行列数 int dps(int i, int j) { int& result = path[i][j]; //读取该点的路径 if (result > 0)//递归结束标志,如果已经计算过就返回该点的最长路径 { return result; } result = 1; int temp = 0; if (i + 1 < rows && map[i][j] > map[i + 1][j])//如果右边的值比自己小,则右移 { temp = dps(i + 1, j) + 1;//递归 if (temp > result)//如果路径比result大,则赋值给result { result = temp; } } if (i - 1 >= 0 && map[i][j] > map[i - 1][j])//如果左边的值比自己小,则左移 { temp = dps(i - 1, j) + 1;//同上 if (temp > result) { result = temp; } } if (j + 1 < cols && map[i][j] > map[i][j+1])//如果上面的值比自己小,则上移 { temp = dps(i, j+1) + 1;//同上 if (temp > result) { result = temp; } } if (j - 1 >= 0 && map[i][j] > map[i][j-1])//如果下边的值比自己小,则下移 { temp = dps(i, j-1) + 1;//同上 if (temp > result) { result = temp; } } if (result > maxResult)//求取最大路径长度 { maxResult = result; } return result; } int main() { while (cin >> rows >> cols) { for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols;++j) { cin >> map[i][j]; } } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { dps(i, j); } } cout << maxResult << endl; } return 0; }