POJ1088 滑雪(动态规划,简单题)

原题链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1088

Description

Michael喜欢滑雪百这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

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= {{-10}{10}{0-1}{01}};
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, 0sizeof(Height));
36        memset(Result, 0sizeof(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}

posted on 2009-02-22 20:39 Philip85517 阅读(237) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年2月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
1234567

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜