矩阵中的最长递增路径
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
示例 2:
输入: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
class Solution {
public static int n,m;
public static int f[][] = new int[1000][1000];
public static boolean check(int x,int y,int nx,int ny,int[][] mat){//能不能走到下一个格子，那些格子可以继续拓展
return x >=0 && y>= 0 && nx >=0 && ny >=0 && x < n && y <m && nx < n && ny <m && mat[x][y] > mat[nx][ny];
}
public int robot(int x,int y,int[][] mat){//最远能走多少步
if(f[x][y] > 0){
return f[x][y];
}
int max = 0;
for(int dx = -1;dx <= 1;dx++){
for (int dy = -1;dy <= 1;dy++){
if(Math.abs(dx + dy) ==1){
if(check(x,y,x+dx,y+dy,mat))
max = Math.max(max,robot(x+dx,y+dy,mat)) ;
}
}
}
f[x][y] = max + 1;
return max+1;
}
//枚举最后出发的位置
public int longestIncreasingPath(int[][] matrix) {
n = matrix.length;
if (n==0){
return 0;
}
m = matrix[0].length;
for(int i = 0;i< n;i++){
for(int j = 0;j < m; j++){
f[i][j] = 0;
}
}
int ans = 0;
for(int i =0;i<n;i++){
for(int j = 0;j<m;j++){
ans = Math.max(ans,robot(i,j,matrix));
}
}
return ans;
}
}