【LeetCode: 2684. 矩阵中移动的最大次数 + dfs】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ dfs
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 💬 共勉

🚩 题目链接

2684. 矩阵中移动的最大次数

⛲ 题目描述

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干正整数组成。

你可以从矩阵第一列中的任一单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值严格大于当前单元格的单元格。
返回你在矩阵中能够移动的最大次数。

示例 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).
可以证明这是能够移动的最大次数。
示例 2：

在这里插入图片描述

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106

🌟 求解思路&实现代码&运行结果

⚡ dfs

🥦 求解思路

该题目可以通过dfs，也可以通过bfs来求解，我们就用dfs来做，感兴趣的同学可以使用bfs。我们从第一列的任一单元格开始，递归右上/右侧/右下三个方向，如果走一步后，没有出界，且格子值大于当前的位置，继续向前走，继续递归过程。在递归的时候，记录每次可以走的最大次数，最后更新答案并返回。
需要注意的是，通过dfs我们会有很多重复计算的过程，所以，我们需要对其进行一个优化的过程，怎么优化呢？首先就必须要明白，重复计算的过程是什么。如果第一行第一列的数值可以想右侧和右下侧移动，并且，第二行第一列的数值和第一行第一列的元素相同，那么它会重复右上和右侧的位置，这个就是重复计算过程。
为了避免这个过程，我们可以将每次递归走过的位置都标记为0，这样就可以保证下次再走的时候不会重复走，避免了重复计算的过程。
有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int max = 0;
        for (int i = 0; i < m; i++) {
            max = Math.max(max, dfs(i, 0, m, n, grid));
        }
        return max;
    }

    public int dfs(int i, int j, int m, int n, int[][] grid) {
        int p1 = 0, p2 = 0, p3 = 0;
        if (i >= 1 && i <= m && j < n - 1 && grid[i - 1][j + 1] > grid[i][j]) {
            p1 = dfs(i - 1, j + 1, m, n, grid) + 1;
        }
        if (i <= m - 1 && j < n - 1 && grid[i][j + 1] > grid[i][j]) {
            p2 = dfs(i, j + 1, m, n, grid) + 1;
        }
        if (i < m - 1 && j < n - 1 && grid[i + 1][j + 1] > grid[i][j]) {
            p3 = dfs(i + 1, j + 1, m, n, grid) + 1;
        }
        grid[i][j] = 0;
        return Math.max(p1, Math.max(p2, p3));
    }
}