滑雪
题目描述
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个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
输入输出样例
输入
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
分析
这题我们可以用记忆化搜索。
因为可以直接返回已经找过的值。
这题每个点出发有可能，所以我们每个点都要开始dfs，最后取他们的最大值。
dfs部分和类似的迷宫差不多,用两个数组表示4个方向：
fi[4]={0,0,1,-1};
fj[4]={1,-1,0,0};
改变方向直接ni=i+fi[k] , nj=j+fj[k]
接下来判断这个方向是否在地图范围内，即
if(ni>0&&ni<=n&&nj>0&&nj<=m)
当然还要判断这个点是否能滑到，也就是高度要前一个低：
if(h[ni][nj]<h[i][j])//a为高度
很明显，因为低的不可能滑向高的，所以我们不需要再开一个数组去记录这个点是否走过。
接下来，就要往四个方向搜索，取四个方向中距离最长的，然后+1，这就是这个点的结果了。
AC代码
#include<iostream>
using namespace std;
int a[105][105],h[105][105],m1,m,ni,nj,n,m2;
int fi[4]={
0,0,-1,1};//四个方向
int fj[4]={
-1,1,0,0};
int dfs(int i,int j)//记忆化搜索
{
if(a[i][j]!=0) return a[i][j];//已经走过就直接返回值
for(int k=0;k<4;k++)//方向
{
ni=i+fi[k];nj=j+fj[k];
if(ni>0&&ni<=n&&nj>0&&nj<=m)if(h[ni][nj]<h[i][j])//判断边界和高度
a[i][j]=max(a[i][j],dfs(ni,nj)+1);//往里面搜索
}
return a[i][j];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>h[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
m1=0,m2=max(m2,dfs(i,j)+1); //找到最大值
cout<<m2;
}
这题我们还可以用动态规划（DP）来做
AC代码
#include<iostream>
#include<algorithm>
using namespace std;
long long n,m,k,num,h[1005][1005],f[1005][1005];
long long nx[4]={
1,-1,0,0};//四个方向
long long ny[4]={
0,0,-1,1};
struct stu//结构体
{
long long x,y,s;
}a[1000005];
bool cmp(stu x,stu y){
return x.s<y.s;}//结构体快排要用到
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>h[i][j];//高度
k++;
a[k].x=i;//方位
a[k].y=j;
a[k].s=h[i][j];
}
sort(a+1,a+k+1,cmp);//进行排序
for(int i=1;i<=k;i++)//每个点
for(int j=0;j<4;j++)//四个反向
{
int dx=a[i].x+nx[j];
int dy=a[i].y+ny[j];
int x=a[i].x;
int y=a[i].y;
if(dx>0&&dx<=n&&dy>0&&dy<=m)//判断出界
if(f[x][y]+1>f[dx][dy]&&h[x][y]<h[dx][dy])//判断符不符合条件
{
f[dx][dy]=f[x][y]+1;if(f[dx][dy]>num) num=f[dx][dy];}
}
cout<<num+1;//还有本身
}
京公网安备 11010502036488号