衣橱整理

LCR 130. 衣橱整理

思路

首先需要理解题意，我刚开始理解为在一个矩阵中找到所有符合digit(i)+digit(j)<=cnt的个数。如下图我以为是找出蓝色格子数量。

实际并不是，只要找到从(0,0)触发，能通过向下或向右走一格能到达的符合digit(i)+digit(j)<=cnt的格子的个数。也就是说要找的是从（0，0）出发通过右移或下移一格能到达的蓝色格子的个数。

题解和网友说要用到深度优先遍历。

function wardrobeFinishing(m, n, cnt) {
  const digitSum = (num) => {
    let sum = 0
    while (num) {
      sum += num % 10
      num = Math.floor(num / 10)
    }
    return sum
  }

  const visited = Array.from({ length: m }, () => Array(n).fill(false))
  let count = 0

  const dfs = (i, j) => {
    if ( i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || digitSum(i) + digitSum(j) > cnt)
      return
    visited[i][j] = true
    count++
    dfs(i + 1, j) // 向下移动
    dfs(i, j + 1) // 向右移动
  }

  dfs(0, 0) // 从(0, 0)开始搜索
  return count
}