题源:滑雪 POJ - 1088
题目:
Glory非常喜欢玩滑滑梯游戏,下面给出了一个n,m的滑道,其中的数字表示滑道的高度。Glory可以从一个点出发向下滑行,每次只能滑行到相邻的位置(上下左右)中高度严格低于当前高度的地方,不能重复划行已经滑行过的地方,但他希望在这个滑道上滑行尽量远的距离,也即是找一条最长的滑道。
Input
第一行输入两个数n,m代表滑梯范围行n和列m(1 <= n,m <= 100)。下面是n行,每行有m个整数,代表高度h,(0<=h<=20000)
Output
输出一个值,代表Glory能够在滑滑梯上面滑行的最长长度是多少
Sample Input
3 3
9 1 2
5 6 7
8 4 3
Sample Output
4
Sample Input
4 7
7 6 5 4 3 2 1
1 5 1 1 1 1 1
1 4 3 1 1 1 1
1 5 6 7 8 1 1
Sample Output
7
标准的记忆化搜索,当然你也可以暴力dfs,应该会超时;
一个点一个点的来,对每一个向四周扩散,找比他大的点,然后记录每个点走到尽头的步数,假如有一次从4到10,一共走了6步,那么这个点dp[x][y]=6;下次从1到10的步数就是,3+dp[x][y];
AC代码:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
int dp[101][101];
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int mapp[101][101];
int n,m;
bool check(int x,int y)
{
if(x<=0||x>n||y<=0||y>m) return 0;
return 1;
}
int dfs(int x,int y)
{
int maxlen=1;
int len;
if(dp[x][y]) return dp[x][y];
for(int i=0;i<4;i++)
{
int xx=x+dir[i][0];
int yy=y+dir[i][1];
if(check(xx,yy)&&mapp[xx][yy]>mapp[x][y])
{
len=dfs(xx,yy)+1;
maxlen=max(len,maxlen);
}
}
return dp[x][y]=maxlen;
}
int main ()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> mapp[i][j];
memset(dp, 0, sizeof(dp));
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
dp[i][j] = dfs(i,j);//依次对每一个点进行搜索;
ans = max(ans, dp[i][j]);
}
cout << ans << endl;
return 0;
}