1 滑雪 
 2 Time Limit:1000MS  Memory Limit:65536K
 3 Total Submit: 11034  Accepted: 3437  
 4
 5 Description
 6 Michael 喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个 区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 
 7
 8
 9  
10
11 Input
12 输入的第一行表示区域的行数R和列数C( 1   <=  R,C  <=   100 )。下面是R行，每行有C个整数，代表高度h， 0 <= h <= 10000 。
13
14 Output
15 输出最长区域的长度。
16
17 Sample Input
18
19 5    5
20 1    2    3    4    5
21 16   17   18   19   6
22 15   24   25   20   7
23 14   23   22   21   8
24 13   12   11   10   9
25
26 Sample Output
27 25
28

 1 #include < stdio.h >
 2 #include < string .h >
 3 #define  MAX 100
 4
 5 struct  point
 6 {
 7      int  x,y,height;
 8 } points[MAX * MAX];
 9
10 int  cmp( void   const   * a,  void   const   * b)
11 {   
12      return  ( * ( struct  point * )a).height  -  ( * ( struct  point * )b).height;
13 } int  path[MAX][MAX];
14
15 int  hills[MAX][MAX];
16 const   int  direction[ 4 ][ 2 ]  =   {  { 0 , 1 } , { 0 , - 1 } , { 1 , 0 } , { - 1 , 0 } } ;
17
18 int  main()
19 {        
20      int  r, c, i, j, k, ans, x, y;
21     scanf( " %d%d " ,  & r,  & c);
22     k  =   0 ;
23      for  (i  =   0 ; i  <  r;  ++ i)
24          for  (j  =   0 ; j  <  c;  ++ j)
25          {
26             scanf( " %d " ,  & hills[i][j]);
27             points[k].x  =  i;
28             points[k].y  =  j;
29             points[k ++ ].height  =  hills[i][j];
30         }
31         
32         qsort(points, k,  sizeof ( struct  point), cmp);
33
34          for  (i  =   0 ; i < r; i ++ )
35              for  (j  =   0 ; j  < c;j ++ )
36                 path[i][j]  =   0 ;    ans  =   0 ;
37             
38              for  (i = 0 ; i < k;  ++ i)
39              {
40                  for  (j = 0 ;j < 4 ; ++ j)
41                  {
42                     x = points[i].x + direction[j][ 0 ];
43                     y = points[i].y + direction[j][ 1 ];
44                      if  (x >= 0 && x < r && y >= 0 && y < c && hills[x][y] < points[i].height && path[points[i].x][points[i].y] <= path[x][y])
45                         path[points[i].x][points[i].y] = path[x][y] + 1 ;
46                 }
47                  if  (ans <= path[points[i].x][points[i].y])
48                     ans = path[points[i].x][points[i].y];
49             }
50             printf( " %d\n " ,ans + 1 );
51              return   0 ;
52 }

刘超 2007-08-23 15:30 发表评论

刘超 2007-08-23 13:15 发表评论