滑雪

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 60769		Accepted: 22147

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 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

Sample Output

25

Source

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;//点的个数 100*100=10000个//整个区域int map[101][101];//用来标记该点是否到过int mark[101][101];//方向坐标，上 下 左 右int dir[4][2] = {-1,0,1,0,0,-1,0,1};//区域的行数和列数int row,column;//输入void put_in(){    cin>>row>>column;    for(int i = 1; i <= row; ++i)    for(int j = 1; j <= column; ++j)    cin>>map[i][j];}int dfs(int px,int py){    //记录这一点到最后所用的步子    int steps;    //记录这一点到最后所用的步子，当有新的方向比目前的步子长，就更新    int max_step = 0;    //首先判断该点以前是否有计算过，若计算过则直接可以使用    if(mark[px][py]!=0)    return mark[px][py];    //从上下左右四个方向进行递归运算    //1、上方    for(int i = 0; i < 4; i++)    {        int x,y;        x = px + dir[i][0];        y = py + dir[i][1];        //判断边界        if(x<1||x>row||y<1||y>column)        continue;        if(map[px][py]>map[x][y])        {            //可以进入            steps = dfs(x,y)+1;            //如果比原来的有更长的步子，就更新他            if(steps > max_step)            max_step = steps;        }    }    //这里的赋值是为了以后再次查询到这里时，可以直接使用而不必再次计算    return  mark[px][py] = max_step;}int main(){    int tem,maxtem=0;    put_in();    memset(mark,sizeof(mark),0);    for(int i = 1;i <= row ; i++)    for(int j = 1;j <= column ;j++)    {        tem = dfs(i,j);        if(tem>maxtem)        maxtem = tem;    }    cout<
        
         <
        
       
      
     

测试数据及答案：

5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 91 111 21 21 3 1 3 22 21 2 4 32 2 1 2 3 44 77 6 5 4 3 2 11 5 1 1 1 1 11 4 3 1 1 1 11 5 6 7 8 1 13 39 1 25 6 78 4 33 41 2 3 48 7 6 59 10 11 123 30 0 00 5 00 0 012 131   1 30  4  800  6  7  8  99 10 1223 120 30 30 4 16 15 14 13 12 11 121 22 99 444444 88 9926 27 9928 9929 3000 456 140 39 1 90 36 35 34 33 3992 30001 789  141 42 4000 44  88 46 47 48 49 50 897  11 59 1 57 56  85 54 53 52 51 908 161 77 56 64 444 66 67 68 69 70 1234 180 79 78 77 76 75 74 73 72 71 12345 181 82 2  2 4 86 5 88 8 90 3456  1100 99 98 97 96 95 94 93 92 91 567 1890 654 623 154 683 15414 86549 633 123 456 123456  19517 45632 643164 3478643 43 16 431 64453132 689431 746546 15643 164543 13146543 13474 314789 4352154 65431 631 654324 65132 89547  34567312 1 113 121   1 30  4  800  6  7  8  99 10 1223 120 30 30 4 16 15 14 13 12 11 121 22 99 444444 88 9926 27 9928 9929 3000 456 140 39 1 90 36 35 34 33 3992 30001 789  141 42 4000 44  88 46 47 48 49 50 897  11 59 1 57 56  85 54 53 52 51 908 161 77 56 64 444 66 67 68 69 70 1234 180 79 78 77 76 75 74 73 72 71 12345 181 82 2  2 4 86 5 88 8 90 3456  1100 99 98 97 96 95 94 93 92 91 567 1890 654 623 154 683 15414 86549 633 123 456 123456  19517 45632 643164 3478643 43 16 431 64453132 689431 746546 15643 164543 13146543 13474 314789 4352154 65431 631 654324 65132 89547  34567312 1 13 30 1 21 0 12 1 03 30 0 00 0 00 0 01 1010 101 2 300 4 5 6 7 8 9 1020 19 18 17 16 15 14 13 12 1121 22 23 24 25 26 27 28 29 3040 39 38 37 36 35 34 33 32 3141 42 43 44 45 46 47 48 49 5060 59 58 57 56 55 54 53 52 5161 62 63 64 65 66 67 68 69 7080 79 78 77 76 75 74 73 72 7181 82 83 84 85 86 87 88 89 90100 99 98 97 96 95 94 93 92 914 41 2 3 41 2 3 41 2 3 41 2 3 44 41 2 2 11 4 4 11 3 3 11 2 2 13 39 1 25 6 78 4 3/////251224374122273731197444