现在的位置: 首页 > 综合 > 正文

POJ 1088 滑雪

2014年08月29日 ⁄ 综合 ⁄ 共 1141字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<memory.h>

using namespace std;

#define INF 0xfffffff

#define MAX 101
int c,r;

struct Node
{
    int height;
    bool visited;//保存该节点是否被访问过,避免不必要的重复计算 
    int length;//从该节点开始能被访问的最大长度 
};

Node node[MAX][MAX];

int findLength(int x,int y)
{
    int top=0,down=0,left=0,right=0;
    int max=0,tmp1=0,tmp2=0;
    if(node[x][y].visited)//如果已经有保存长度了就避免重复计算 
        return node[x][y].length;
    
    node[x][y].visited=true;
    
    //right
   if ( x < c - 1 && node[x][y].height < node[x +1][y].height)
    right = 1 + findLength ( x + 1 , y );
   
    //left
   if ( x > 0 && node[x][y].height < node[x - 1][y].height )
    left = 1 + findLength ( x - 1 , y );
   
    //down
   if (( y < r - 1) && node[x][y].height < node[x][y + 1].height )
     down = 1 + findLength (x , y + 1 );
   
    //top
   if (( y > 0) && node[x][y].height < node[x][y - 1 ].height )
     top = 1 + findLength ( x , y - 1 );
   
   tmp1 = left > right ? left : right;
   tmp2 = down > top ? down : top;
   max = tmp1 > tmp2 ? tmp1 : tmp2;
   
  node[x][y].length = max;
  return max;
}

int main()
{
    cin >> c >> r;
    for(int i=0;i<c;++i)
    {
        for(int j=0;j<r;++j)
        {
            cin >> node[i][j].height;
            node[i][j].length=0;
            node[i][j].visited=false;
        }
    }
    int tmp=0,max=0;
    for(int i=0;i<c;++i)
    {
        for(int j=0;j<r;++j)
        {
            tmp=findLength(i,j);
            max=tmp>max?tmp:max;
        }
    }
    cout << max+1 << endl;
    return 0;
}

抱歉!评论已关闭.