首页 > 代码库 > 滑雪（动规）

滑雪（动规）

2024-09-13 11:36:23   218人阅读

滑雪
【问题描述】
        小明喜欢滑雪，因为滑雪的确很刺激，可是为了获得速度，滑的区域必须向下倾斜，当小明滑到坡底，不得不再次走上坡或等着直升机来载他，小明想知道在一个区域中最长的滑坡。滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：
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-24-17-16-1（从25开始到1结束），当然25-24……2…1更长，事实上这是最长的一条。
【输入格式】
        输入的第一行为表示区域的二维数组的行数R和列数C（1≤R、C≤100）下面是R行，每行有C个数代表高度。
【输出格式】
        输出区域中最长的滑坡长度。
 
【输入样例】ski.in
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
【输出样例】ski.out
25
【思路】：记忆化搜索 
【代码】
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 int map[101][101],f[101][101],m,n;
 6 int dx[4]={-1,0,1,0},
 7     dy[4]={0,1,0,-1};
 8 int search(int,int);
 9 int main()
10 {
11     int ans=-1,tmp;
12     scanf("%d%d",&m,&n);
13     for(int i=1;i<=m;i++)
14         for(int j=1;j<=n;j++)
15             scanf("%d",&map[i][j]);//输入每个点的高度 
16     for(int i=1;i<=m;i++)
17       {
18           for(int j=1;j<=n;j++)
19            {
20                  tmp=search(i,j);//tmp为从（i，j）开始滑的长度 
21                 if(tmp>ans)//更新最大值 
22                 {
23                     ans=tmp;
24             } 
25             f[i][j]=tmp;//记录从(i,j)开始滑的长度    
26          }
27       }
28       printf("%d\n",ans);
29       return 0;
30 }
31 int search(int x,int y)//记忆化搜索 
32 {
33     if(f[x][y])//如果已经搜索过（搜索过就赋值了）；
34     return f[x][y];//直接返回 
35     int t=1,maxl;
36     for(int i=0;i<=3;i++)//否则开始搜索，上下左右 
37     {
38         int xx=x+dx[i],yy=y+dy[i];//新坐标 
39         if(xx>=1&&xx<=m&&yy>=1&&y<=n&&map[xx][yy]<map[x][y])//没有出范围并且能够滑 
40         {
41          maxl=search(xx,yy)+1;//步数就等于从新坐标滑的步数+1（加入的1为现在的坐标） 
42          if(maxl>t)//选择最大值 
43          t=maxl;    
44         }
45     }
46     f[x][y]=t;//赋值 
47     return t;
48 }

 

滑雪（动规）


联系
我们