滑雪是一项非常刺激的运动,为了获得速度,滑雪的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。
给出一个由二维数组表示的滑雪区域,数组的数字代表各点的高度。请你找出这个区域中最长的滑坡。
下面是一个例子:
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更长。事实上,这是最长的一条滑坡。
输入描述:
输入第一行为两个数R, C,表示滑雪区域的行数和列数(1≤R,C≤100)
下面是R行,每行有C个整数,表示高度H(0≤H≤10000)。
输出描述:
输出一行,只包含一个整数,表示滑雪区域中最长滑坡的长度。
#include <bits/stdc++.h>
using namespace std;
int a[10001][10001],x[10001],y[10001],a2[10001];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int r,c,ma,s;
int ans=0;
void dfs(int x,int y)
{
int tx,ty;
ma=max(ma,s);
for(int i=0;i<=3;i++)
{
tx=x+dx[i];
ty=y+dy[i];
if(ty>c||tx>r||tx<1||ty<1) continue;
if(a[tx][ty]<a[x][y]){
s+=1;
dfs(tx,ty);
s-=1;
}
}
}
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=r*c;i++)
{
x[i]=floor(i/r)+1;
y[i]=i%c;
int x2=x[i];
int y2=y[i];
a2[i]=a[x2][y2];
}
for(int i=1;i<=r*c-1;i++)
{
for(int j=i+1;j<=r*c;j++)
{
if(a2[i]<a2[j])
{
swap(a2[i],a2[j]);
swap(x[i],x[j]);
swap(y[i],y[j]);
}
}
}
dfs(x[1],y[1]);
dfs(x[2],y[2]);
dfs(x[3],y[3]);
dfs(x[4],y[4]);
dfs(x[5],y[5]);
dfs(x[6],y[6]);
dfs(x[7],y[7]);
dfs(x[8],y[8]);
dfs(x[9],y[9]);
dfs(x[10],y[10]);
dfs(x[11],y[11]);
dfs(x[12],y[12]);
dfs(x[13],y[13]);
dfs(x[14],y[14]);
dfs(x[15],y[15]);
dfs(x[16],y[16]);
dfs(x[17],y[17]);
dfs(x[18],y[18]);
dfs(x[19],y[19]);
dfs(x[20],y[10]);
dfs(x[21],y[21]);
dfs(x[22],y[22]);
dfs(x[23],y[23]);
dfs(x[24],y[24]);
dfs(x[25],y[25]);
dfs(x[26],y[26]);
dfs(x[27],y[27]);
dfs(x[28],y[28]);
dfs(x[29],y[29]);
dfs(x[30],y[30]);
dfs(x[31],y[31]);
dfs(x[32],y[32]);
dfs(x[33],y[33]);
dfs(x[34],y[34]);
dfs(x[35],y[35]);
dfs(x[35],y[35]);
cout<<ma+1<<endl;
return 0;
}