活蹦乱跳的香穗子
香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值
跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.
香穗子可以从任意的格子出发,在任意的格子结束,
那么她最多能跳几次?
输入:
第一行n,m,表示田野的长和宽
接下来n行,每行m个数,表示该格的价值
输出:
一个数,表示最多跳得格数
Sample Input
2 2
2 5
-1 3
Sample Output
3
数据范围:
n,m<=100
答案保正小于Maxlongint
类似滑雪，一个记忆化搜索即可
C++ Code
/*
C++ Code
http://blog.csdn.net/jiangzh7
*/
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
int n,m,a[MAXN][MAXN],f[MAXN][MAXN];
int getmax(int x,int y)
{
if(x>n||x<1||y>m||y<1)return 0;
if(f[x][y]!=-1)return f[x][y];
f[x][y]=1;
for(int i=1;i<=4;i++)
if(a[x][y]<a[x+dx[i]][y+dy[i]])
f[x][y]>?=getmax(x+dx[i],y+dy[i])+1;
return f[x][y];
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
int max=0;
memset(f,-1,sizeof(f));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
max>?=getmax(i,j);
printf("%d",max);
return 0;
}
