矩阵中移动的最大次数

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 解释：从第一列的任一单元格开始都无法移动。

解题思路： @@@ dfs 解法

遍历每一行的第一个单元格，以该单元格为起点进行深度优先搜索。
在搜索过程中，递归地探索相邻单元格，并更新移动的最大次数。
使用一个二维数组 visited 来记录已经访问过的单元格，避免重复访问。
在搜索过程中，根据移动条件更新移动的最大次数 maxCount。
返回最大移动次数 maxCount 作为结果。

func maxMoves(grid [][]int) int {
      m, n := len(grid), len(grid[0])
      
      maxCount := 0
      dirs := [][]int{{-1, 1}, {0, 1}, {1, 1}}
      
      var dfs func(i, j int, visited [][]bool) int
      dfs = func(i, j int, visited [][]bool) int {
          if i < 0 || i >= m || j < 0 || j >= n || visited[i][j] {
              return 0
          }
          visited[i][j] = true
          count := j
          for _, dir := range dirs {
              newi, newj := i+dir[0], j+dir[1]
              if newi >= 0 && newi < m && newj >= 0 && newj < n && grid[newi][newj] > grid[i][j] {
                  count = max(count, dfs(newi, newj, visited))
              }
          }
          return count
      }
      
      for i := 0; i < m; i++ {
          visited := make([][]bool, m)
          for j := range visited {
              visited[j] = make([]bool, n)
          }
          count := dfs(i, 0, visited)
          maxCount = max(maxCount, count)
      }
      return maxCount
  }
  
  func max(a, b int) int {
      if a > b {
          return a
      }
      return b
}

@@@

cs-book

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