The Growning Pains

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

解题思路：没什么好说的，从最低的开使迭代，寻找周围比它低的点，找出最大的结果继承。
代码：

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4using namespace std;
 5#define MAXN 210
 6
 7int Height[MAXN][MAXN];
 8int Result[MAXN][MAXN];
 9int Direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
10typedef struct Node
11{
12    int x, y;
13    int ih;
14}NodeType;
15
16vector<NodeType> v;
17
18bool cmp1(NodeType a, NodeType b)
19{
20    if(a.ih < b.ih) return true;
21    return false;
22}
23
24int main()
25{
26    int iRow, iColumn;
27    int i, j;
28    int iNext_x, iNext_y;
29    int iMaxLen;
30    int iTempLen;
31    NodeType SBuf;
32    
33    while(scanf("%d%d", &iRow, &iColumn) != EOF)
34    {
35        memset(Height, 0, sizeof(Height));
36        memset(Result, 0, sizeof(Result));
37        v.clear();
38        for(i = 0; i < iRow; i++)
39        {
40            for(j = 0; j < iColumn; j++)
41            {
42                scanf("%d", &Height[i][j]);
43                SBuf.ih = Height[i][j];
44                SBuf.x = i;
45                SBuf.y = j;
46                v.push_back(SBuf);
47            }
48        }
49
50        sort(v.begin(), v.end(), cmp1);
51        iMaxLen = -1;
52        for(i = 0; i < v.size(); i++)
53        {
54            iTempLen = -1;
55            for(j = 0; j < 4; j++)
56            {
57                iNext_x = v[i].x + Direction[j][0];
58                iNext_y = v[i].y + Direction[j][1];
59                if(iNext_x >= 0 && iNext_x < iRow && iNext_y >= 0 && iNext_y < iColumn)
60                {
61                    if(v[i].ih > Height[iNext_x][iNext_y] && iTempLen < Result[iNext_x][iNext_y])
62                    {
63                        iTempLen = Result[iNext_x][iNext_y];
64                    }
65                }
66            }
67            Result[v[i].x][v[i].y] = iTempLen + 1;
68            if(Result[v[i].x][v[i].y] > iMaxLen) iMaxLen = Result[v[i].x][v[i].y];
69        }
70        printf("%d\n", iMaxLen + 1);
71    }
72    return 0;
73}