刚才写过了dfs的方法
现在回顾一下dp算法
dp的算法看起来比dfs 好理解的多 当然dfs设计复杂的递归本来就不是一种好理解的算法。
我们首先用struct data 存储节点
这个节点是由坐标和 height值组成的。
data arr【maxn】;
具体步骤就是输入 赋值arr数组
然后从小到大排序
我们的思想是从height最小的那个点开始
探查它的上下左右四个点 一旦发现比它大的 并且dp值可以更新的就更新
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10005;
struct Data{
int x,y,h;};
Data arr[maxn];
int height[105][105];
int dp[105][105];
bool Cmp(const Data & a,const Data & b)
{
return a.h<b.h;
}
int i,j,k,c,r;
int main()
{
scanf("%d%d",&c,&r);
int index=0;
for(i=1;i<=c;++i)
{
for(j=1;j<=r;++j)
{
arr[index].x=i;
arr[index].y=j;
scanf("%d",&arr[index].h);
height[i][j]=arr[index].h;
dp[i][j]=1;
index++;
}
}
sort(arr,arr+c*r,Cmp);
for(i=0;i<c*r;++i)
{
if(height[arr[i].x+1][arr[i].y]>arr[i].h)
{
if(dp[arr[i].x+1][arr[i].y]<dp[arr[i].x][arr[i].y]+1)
dp[arr[i].x+1][arr[i].y]=dp[arr[i].x][arr[i].y]+1;
}
if(height[arr[i].x-1][arr[i].y]>arr[i].h)
{
if(dp[arr[i].x-1][arr[i].y]<dp[arr[i].x][arr[i].y]+1)
dp[arr[i].x-1][arr[i].y]=dp[arr[i].x][arr[i].y]+1;
}
if(height[arr[i].x][arr[i].y+1]>arr[i].h)
{
if(dp[arr[i].x][arr[i].y+1]<dp[arr[i].x][arr[i].y]+1)
dp[arr[i].x][arr[i].y+1]=dp[arr[i].x][arr[i].y]+1;
}
if(height[arr[i].x][arr[i].y-1]>arr[i].h)
{
if(dp[arr[i].x][arr[i].y-1]<dp[arr[i].x][arr[i].y]+1)
dp[arr[i].x][arr[i].y-1]=dp[arr[i].x][arr[i].y]+1;
}
}
int max=1;
for(i=1;i<=c;++i)
{
for(j=1;j<=r;++j)
{
if(dp[i][j]>max)
max=dp[i][j];
}
}
printf("%d\n",max);
return 0;
}