今天在做题的时候,遇到一道搜索题.
描述
C teacher喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而
且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。C想知道在一个区域中最长的滑
坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
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(从24开始,在1结束)。当然25 24 23 3 2 1更长。事实上,这是
最长的一条。
输入
输入的第一行为表示区域的二维数组的行数R和列数C(1≤R,C≤100)。下面是R行,每行有C个数,代
表高度(两个数字之间用1个空格间隔)。
输出
输出区域中最长滑坡的长度。
输入样例 1
输出样例 1
5 5
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
25
运行后我超时了
希望有人作详细的注释解析,我在网上看了没懂!
#include <bits/stdc++.h>
using namespace std ;
const int N = 1010 ;
int n , m , res ;
int g[N][N] , f[N][N] ;
int dx[4] = {-1 , 0 , 1 , 0} , dy[4] = {0 , 1 , 0 , -1} ;
int dp (int x , int y)
{
int & v = f[x][y] ;
if (v != -1) return v ;
else v = 1 ;
for (int i = 0; i < 4; i++)
{
int xx = x + dx[i] , yy = y + dy[i] ;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[x][y] > g[xx][yy])
{
v = max (v , dp (xx , yy) + 1) ;
}
}
return v ;
}
int main ()
{
cin >> n >> m ;
memset (f , -1 , sizeof (f)) ;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) cin >> g[i][j] ;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++) res = max (res , dp (i , j)) ;
}
cout << res << endl ;
return 0 ;
}
首先要先理解题意