动力扣每日一题 2024/3/16 矩阵中的最大移动次数

前言：首先这个系列不一定会连续更新下去 也许会断更 目前只打算更新每日一题的easy和medium难度 会逐步讲解每一行代码的思路

题目描述

用例说明

思路讲解

最外层遍历：将第一列的每一个元素看作一次遍历的起点（初始值）

返回值是移动的最大次数 用ans来存储

很容易想到用深度优先搜索 dfs内的参数是什么呢？首先得有横纵坐标，以及整个二维矩阵，ans可以定义为全局变量，不必再加入dfs内。

dfs内的处理逻辑：首先需要更新ans，ans的值和横坐标取最大值 最大不超过矩阵的长度

dfs的本质是递归 递归的出口就是当走到矩阵右边界的时候 即ans==grid[0].length-1

dfs（i，0，gird）是指从（i，0）坐标开始找符合位置条件的且值比他大的下一个元素

由于走动的格子受到方向的限制，只能走右上，右下和右，所有在遍历的时候需要对始末位置取最大最小值，最小不能小于0，最大不能大于数组列的长度

当前节点深度优先搜索之后需要将其中的值置0表示已经访问过了

代码

class Solution {
    int ans;
    public int maxMoves(int[][] grid) {
      for(int i=0;i<grid.length;i++){
        dfs(i,0,grid);
      }
      return ans;
    }
    public void dfs(int i,int j,int[][] grid){
        ans=Math.max(ans,j);
        if(ans==grid[0].length-1){
            return;
        }
        for(int k=Math.max(i-1,0);k<Math.min(i+2,grid.length);k++){
            if(grid[k][j+1]>grid[i][j]){
                dfs(k,j+1,grid);
            }
        }
        grid[i][j]=0;
    }
}

复杂度

时间复杂度O(mn)

空间复杂度O(n)