AcWing 901. java同学
原题链接
简单
作者:
季之秋
,
2021-02-19 23:10:36
,
所有人可见
,
阅读 257
import java.util.*;
public class Main{
static int N=310,n,m;
static int[][] f=new int[N][N]; //从i j开始的可以经过所有点的数最大值
static int[][] w=new int[N][N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++){
Arrays.fill(f[i],-1); //初始化记忆搜索
for(int j=1;j<=m;j++)
w[i][j]=sc.nextInt();
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
res=Math.max(res,dp(i,j)); //每个点开始的最大值
}
System.out.println(res);
}
static int[] dx={-1,0,1,0},dy={0,1,0,-1}; //偏移数组
static int dp(int x,int y){
if(f[x][y] !=-1) return f[x][y]; //遍历过说明已经确定最大值了,不用考虑其他点有没有确定
f[x][y]=1; //这个点自己就是一个点,
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a<=n&&a>=1&&b>=1&&b<=m&&w[a][b]<w[x][y]) //不出界而且有效
f[x][y]=Math.max(f[x][y],dp(a,b)+1); //递归代替循环f[a][b],代码短
}
return f[x][y];
}
}