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