P1434 [SHOI2002]滑雪（DFS）（DP）

滑雪

题目描述
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;//还有本身
} 

谢谢观看