?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
?? 作者簡介：碩風(fēng)和煒，CSDN-Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者??，保研|國家獎學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？????

?? 題目鏈接

• 2684. 矩陣中移動的最大次數(shù)

? 題目描述

給你一個下標從 0 開始、大小為 m x n 的矩陣 grid ，矩陣由若干 正 整數(shù)組成。

你可以從矩陣第一列中的 任一 單元格出發(fā)，按以下方式遍歷 grid ：

從單元格 (row, col) 可以移動到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三個單元格中任一滿足值 嚴格 大于當(dāng)前單元格的單元格。
返回你在矩陣中能夠 移動 的 最大 次數(shù)。

示例 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).
  可以證明這是能夠移動的最大次數(shù)。
  示例 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

?? 求解思路&實現(xiàn)代碼&運行結(jié)果

? dfs

?? 求解思路

1. 該題目可以通過dfs，也可以通過bfs來求解，我們就用dfs來做，感興趣的同學(xué)可以使用bfs。我們從第一列的任一單元格開始，遞歸右上/右側(cè)/右下三個方向，如果走一步后，沒有出界，且格子值大于當(dāng)前的位置，繼續(xù)向前走，繼續(xù)遞歸過程。在遞歸的時候，記錄每次可以走的最大次數(shù)，最后更新答案并返回。
2. 需要注意的是，通過dfs我們會有很多重復(fù)計算的過程，所以，我們需要對其進行一個優(yōu)化的過程，怎么優(yōu)化呢？首先就必須要明白，重復(fù)計算的過程是什么。如果第一行第一列的數(shù)值可以想右側(cè)和右下側(cè)移動，并且，第二行第一列的數(shù)值和第一行第一列的元素相同，那么它會重復(fù)右上和右側(cè)的位置，這個就是重復(fù)計算過程。
3. 為了避免這個過程，我們可以將每次遞歸走過的位置都標記為0，這樣就可以保證下次再走的時候不會重復(fù)走，避免了重復(fù)計算的過程。
4. 有了基本的思路，接下來我們就來通過代碼來實現(xiàn)一下。

?? 實現(xiàn)代碼

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));
    }
}

?? 運行結(jié)果

?? 共勉

文章來源地址http://www.zghlxwxcb.cn/news/detail-841588.html

到了這里，關(guān)于【LeetCode: 2684. 矩陣中移動的最大次數(shù) + dfs】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！