题目描述

香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值

跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.

香穗子可以从任意的格子出发,在任意的格子结束,

那么她最多能跳几次?

输入输出格式

输入格式：

第一行n,m,表示田野的长和宽

接下来n行,每行m个数,表示该格的价值

输出格式：

一个数,表示最多跳得次数

这题挺简单的，主要是记忆化搜索。

模板代码如下：

include<cstdio> //一大堆头文件

#include<iostream> using namespace std; int map[1005][1005]={0}; //存地图的数字 int f[1005][1005]; //状态转移数组 int fx[]={0,0,1,-1},fy[]={1,-1,0,0}; //简称跑路数组 int n,m,ans; //边界and答案 bool in(int tx,int ty,int x,int y){ //剪枝函数 if(tx>=0&&ty>=0&&tx<=n&&ty<=m&&map[tx][ty]>map[x][y])return true; //按题目条件来 return false; } int dfs(int x,int y){ //！！！经典记忆化搜索 if(f[x][y]>0)return f[x][y]; for(int i=0;i<4;i++){ //枚举方向 int tx=x+fx[i]; int ty=y+fy[i]; if(in(tx,ty,x,y) )f[x][y]=max(f[x][y],dfs(tx,ty)+1); } return f[x][y]; } int main(){ cin>>n>>m; for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>map[i][j]; //输入 for(int i=0;i<n;i++)for(int j=0;j<m;j++)ans=max(ans,dfs(i,j)); //枚举每个起始位置 cout<<ans; //输出答案 return 0; //end... } 很简单，是不是。