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}