是算法的问题还是代码的问题?

P1434 [SHOI2002] 滑雪

CUFT @ 2019-04-20 17:25:12

这道题我的想法是用一个二维结构体数组来存地图,map[x][y].Hight表示高度,map[x][y].Length表示以(x,y)能下滑的最大长度,初始化为0.其中地图外面还有一圈“围墙”,高度为inf。

那么不难得到,假设在某个方向上(比如说向上)可以划过去,那么map[x][y].Length = map[x][y-1].Length + 1,以此类推,把每个点的四个方向都遍历一遍,就可以找到最长了。

代码如下:

#include <iostream>
#define Max(a,b) (a)>(b) ? (a) : (b)
#define Inf 0x3f3f3f3f
using namespace std;

struct Point{
    int Hight;
    int Length;
}map[105][105];

int f(int x,int y) {
    if( map[x][y].Length == 0 ) {
        int h = map[x][y].Hight;
        int U = map[x][y-1].Hight>h ? 0 : f(x,y-1);
        int D = map[x][y+1].Hight>h ? 0 : f(x,y+1);
        int L = map[x-1][y].Hight>h ? 0 : f(x-1,y);
        int R = map[x+1][y].Hight>h ? 0 : f(x+1,y);
        map[x][y].Length = 1 + Max(Max(U,D),Max(L,R));
    }
    return map[x][y].Length;
}
int main(){
    int c,r,ans=0;
    cin>>c>>r;
    for(int i=0;i<=c+1;i++){
        for(int j=0;j<=r+1;j++){
            if( i==0 || j==0 || i==c+1 || j==r+1)
                map[i][j].Hight = Inf;
            else
                cin>>map[i][j].Hight;
            map[i][j].Length = 0;
        }
    }
    for(int i=1;i<=c;i++)
        for(int j=1;j<=r;j++)
            ans = Max(ans,f(i,j));
    cout<<ans;  
    return 0;
}

4WA6MLE


|