P1434 滑雪
题目描述
Michael喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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：
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
输出样例#1：
25
思路:
记忆化搜索!!!要注意的是需要开一个数组s记录下来已经搜索过的最大值,速度极大提高!!!
坑点:
1)其实是不需要开v数组并且回溯的,因为能够AC,但是我想不明白为什么不用回溯???因为一块只能走一次啊!!!!为什么???
2)需要用dfs搜到的答案加1(天知道为什么啊!!!!qwq不懂....)
代码:
#include <iostream> #include <cstdio> #include <cmath> using namespace std; const int M = 102; int n,m,ans;///行,列,答案 int t[M][M]; int s[M][M]; int dx[4] = {0, 0,1,-1}, dy[4] = {1,-1,0, 0}; int dfs(int x,int y) { if(s[x][y]) return s[x][y]; else { int num=0,tmp=0; 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) continue; if(t[x][y]>t[xx][yy]) { num=dfs(xx,yy)+1; ///加上自己本身!!! if(num>tmp) { tmp=num;///记录下来,寻找最大值 s[x][y]=num;///用数组进行记录 } } } return tmp; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&t[i][j]); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int now=dfs(i,j); if(now+1>ans) ans=now+1; } } printf("%d",ans); return 0; }