题目
2684. 矩阵中移动的最大次数 - 力扣（LeetCode）
给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
从单元格 (row, col) 可以移动到 (row - 1, col 1)、(row, col 1)和 (row 1, col 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。
示例一：
输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。示例二：
输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。解题
解法一
思路
按照题目，能到达的列数，就是最终的答案，因此我们需要用一个result记录当前最大到达的列数（初始值为-1），便于后面返回，同时用一个dp[][]数组记录每个点的可达情况。
建立一个dp[][]数组，用来存储到达每个单元格是否可达，遍历第一列开始。
用两个for循环进行遍历，第一个for循环遍历列，第二个for循环遍历每一行的每个元素，然后进行扫描，不是第一列的情况下，要是遇到dp[i][j]是0的情况直接跳过本次循环（该点不可达）。
然后一直扫描，要是一趟扫描下来result!=i，证明当前已经无法往前移动了，直接返回result 1即可。等所有都遍历完毕，需要看最后一列中dp[][]是否有可达标记，要是有可达标记 result 1，要是没有可达标记，直接返回result
解决
代码语言：javascript复制class Solution {
public int maxMoves(int[][] grid) {
//建立dp数组，记录可达情况
int[][] dp = new int[grid.length][grid[0].length];
int result=-1;
for(int i=0;i < grid[0].length-1;i ){ //遍历每一列
for(int j=0;j=0?j-1:j][i 1]>grid[j][i]){ //判断右上那个是否符合
dp[j-1>=0?j-1:j][i 1] = 1;
result = i;
}
if(grid[j][i 1]>grid[j][i]){
dp[j][i 1] = 1;
result = i;
}
if(grid[j 1< grid.length?j 1:j][i 1]>grid[j][i]){
dp[j 1< grid.length?j 1:j][i 1] = 1;
result = i;
}
}
if(result!=i){ //证明当前已经无法往前移动了，直接返回结果即可
return result 1;
}
}
//判断最后一列是否有记录
for(int i=0;i< grid.length;i ){
if(dp[i][grid[0].length-1]==1){
result ;
break;
}
}
return result;
}
}结果
代码语言：javascript复制> 2023/07/18 17:41:02
解答成功:
执行耗时:4 ms,击败了93.94% 的Java用户
内存消耗:53.4 MB,击败了76.62% 的Java用户
