【DFS】poj 1088 滑雪

2024-06-14 01:48

文章标签 poj dfs 滑雪 1088

本文主要是介绍【DFS】poj 1088 滑雪，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

滑雪

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 76064		Accepted: 28203

Description

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

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

Sample Output

Source

SHTSC 2002

解题思路：

一看题就立刻会想到搜索DFS，然而这道题和普通的搜索还不太一样，这道题在搜索的过程中要把最大距离给求出来，于是要用到动态规划的思想，

状态转移方程：dp[x][y]=max(dp[x-1][y], dp[x+1][y], dp[x][y-1], dp[x][y+1])+1

于是乎便有了记忆化搜索的产生

具体见代码：

#include <stdio.h>
#include <string.h>
#include <time.h>int map[110][110],ans[110][110];
int r,c;int a[]={1,0,-1,0};
int b[]={0,1,0,-1};int dfs(int x,int y)
{int i,j,k,xx,yy;    if(ans[x][y])return ans[x][y];// 搜索过了就要返回  //递归出口 1 for(i=0;i<4;i++){xx=x+a[i];yy=y+b[i];if(xx>0&&xx<=r&&yy>0&&yy<=c&&map[x][y]>map[xx][yy])// 搜索 + 状态转移方程  //递归出口 2 {          k = dfs(xx,yy);  //记录当前节点的最大值 if(ans[x][y]<k+1)ans[x][y]=k+1;            }} return ans[x][y];  
}int main()
{int i,j,k,max=0;//clock_t start,finish;//1//double total_time;//2scanf("%d%d",&r,&c);memset(map,0,sizeof(map));memset(ans,0,sizeof(ans));for(i=1;i<=r;i++){for(j=1;j<=c;j++)scanf("%d",&map[i][j]);}//start = clock();//3//dfs(1,1);//finish = clock();// 4//total_time = (double)(finish-start)/CLOCKS_PER_SEC;// 5//printf("%lf seconds\n",total_time);// 6for(i=1;i<=r;i++){for(j=1;j<=r;j++){dfs(i,j);if(ans[i][j]>max)//更新 max值 max=ans[i][j];}}printf("%d\n",max+1);system("pause");//while(1);return 0;
}