原题:
滑雪
时间限制: 1 Sec 内存限制: 256 MB题目描述
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。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
输入
第一行表示有几组测试数据,输入的第二行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。 后面是下一组数据;
输出
输出最长区域的长度。
样例输入
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
题意:
在R*C的矩阵中寻一条路径,并使其严格下降,求最长的路径长度。
这道题正解是DP思想中的记忆化搜索,用s数组记录从s[i][j]出发可以到达的最远距离。
怎么思考呢?我们先用暴力dfs来依次枚举每一个点找最长路径(代码不贴了),虽然可以找到最短路径,但很明显会超时。
分析一下思路:每次枚举到一个点的时候,我们都会向它的四个方向拓展,如果高度比当前点低就再次拓展,有时候一个点已经在之前的dfs中枚举过了,再次拓展到这个点的时候需要再尝试一遍,岂不是很浪费?
所以我们试着储存之前尝试过的结果,下次到达一个已经搜索过的点就可以直接调用,节省了很多时间,这也是记忆化搜索的原因和优化方法。
控制方向的简单小技巧:
对于当前点(x,y)而言,它的上、下、左、右坐标分别为(x-1,y),(x+1,y),(x,y-1),(x,y+1),转换方向时相当于直接在原来的坐标上操作,因此我们可以开两个数组dx,dy配套使用,转换方向就在原坐标基础上分别加上dx[i],dy[i],如(不完整代码,(tx,ty)为转方向后的坐标):
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; ... int tx=x+dx[i],ty=y+dy[i];
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace std; 5 int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; 6 //控制方向的常用方法 7 int n,m,a[205][205],s[205][205],ans; 8 int dfs(int x,int y) 9 { 10 if(s[x][y]) return s[x][y]; 11 s[x][y]=1;//自身算一个距离 12 for(int i=0;i<4;i++) 13 { 14 int tx=dx[i]+x,ty=dy[i]+y; 15 if(tx>0 && tx<=n && ty>=1 && ty<=m && a[x][y]>a[tx][ty]) 16 { 17 dfs(tx,ty); 18 s[x][y]=max(s[x][y],s[tx][ty]+1); 19 //记忆化 20 } 21 } 22 return s[x][y]; 23 } 24 int main() 25 { 26 scanf("%d%d",&n,&m); 27 for(int i=1;i<=n;i++) 28 for(int j=1;j<=m;j++) 29 scanf("%d",&a[i][j]); 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=m;j++) 32 ans=max(ans,dfs(i,j));//将每个点当成起点做dfs 33 printf("%d",ans); 34 return 0; 35 }