白熊不爱A @ 2019-10-05 22:17:32
代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
int R,C;//r行c列
int map[101][101],proj[101][101];//rst为周围情况,1上,2下,3左,4右
struct p{
int val,ff,gg;//最长滑道 x y
}rst[6];
void sct(){
proj[1][1]=1;
return;
}
bool cmp(p a,p b){
return a.val>b.val;
}
int prog(int i,int j){
if(proj[i][j]) return proj[i][j];//记忆化
//搜集周围情况
if(i==1) rst[1].val=0; else rst[1].val=prog(i-1,j);//点在第一行
if(i==R) rst[2].val=0; else rst[2].val=prog(i+1,j);//点在第R行
if(j==1) rst[3].val=0; else rst[3].val=prog(i,j-1);//点在第一列
if(i==C) rst[4].val=0; else rst[4].val=prog(i,j+1);//点在第c列
sort(rst+1,rst+4+1,cmp);//排序
int s=1;
//在周围点中找最大的滑道 而且要能划过去
while(s<=4){
if(map[rst[s].ff][rst[s].gg]<=map[i][j]&&rst[s].val!=0){
proj[i][j]=rst[s].val+1;//自己最长滑道=该点最长滑道+1
break;//跳出以防多加
}
s--;
}
return proj[i][j];
}
int main(){
sct();
int max=0;
cin>>R>>C;
for(int i=1;i<=R;++i){
for(int j=1;j<=C;++j){
cin>>map[i][j];
prog(i,j);
}
}
//遍历所有点 找最大值
for(int i=1;i<=R;++i){
for(int j=1;j<=C;++j){
if(proj[i][j]>max){
max=proj[i][j];
}
}
}
cout<<max;
return 0;
}
by zr太弱了 @ 2019-10-05 22:40:16
@白熊不爱A
状态转移方程: