推荐 网页游戏,什么是seo推广,常熟建设设银行网站,常州市住房和城乡建设局网站#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜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));}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
