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

矩阵中移动的最大次数

• 难度: medium
• 原始链接: https://leetcode.cn/problems/maximum-number-of-moves-in-a-grid
• 标签: 深度优先遍历, 广度优先遍历

解法一: 深度优先遍历

go

func maxMoves(grid [][]int) int {
  m := len(grid)
  n := len(grid[0])
  shift := []int{
    -1,
    0,
    1,
  }
  ansMap := make(map[int]int)
  var dfs func(r, c int) int
  dfs = func(r, c int) int {
    if ans, exists := ansMap[r*n+c]; exists {
      return ans
    }
    ans := c - 1
    if c >= n {
      return ans
    }
    for i := 0; i < 3; i++ {
      newR := r + shift[i]
      if newR >= 0 && newR < m && grid[newR][c] > grid[r][c-1] {
        ans = max(ans, dfs(newR, c+1))
      }
    }
    ansMap[r*n+c] = ans
    return ans
  }
  ans := 0
  for i := 0; i < m; i++ {
    ans = max(ans, dfs(i, 1))
  }
  return ans
}

解法二: 广度优先遍历

go

func maxMoves(grid [][]int) int {
  m := len(grid)
  n := len(grid[0])
  for i := 0; i < m; i++ {
    grid[i][0] *= -1
  }
  width := 1
  shift := []int{
    -1,
    0,
    1,
  }
  for width < n {
    isNext := false
    for i := 0; i < m; i++ {
      if grid[i][width-1] > 0 {
        continue
      }
      for j := 0; j < 3; j++ {
        r := i + shift[j]
        if r >= 0 && r < m && grid[r][width] > 0 && grid[r][width] > -grid[i][width-1] {
          isNext = true
          grid[r][width] *= -1
        }
      }
    }
    if !isNext {
      break
    }
    width++
  }
  return width - 1
}