13. 机器人的运动范围

来源

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

题目

地上有一个 m 行 n 列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格 [35, 37] ，因为 3+5+3+7=18。但它不能进入方格 [35, 38]，因为 3+5+3+8=19。请问该机器人能够到达多少个格子？

示例:

示例 1.

输入：m = 2, n = 3, k = 1
输出：3

示例 2.

输入：m = 3, n = 1, k = 0
输出：1

提示：

• 1 <= n,m <= 100
• 0 <= k <= 20

思路

图，深度优先，回溯法 跟上一题很相似。

解题

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
  const visited = new Array(n).fill(0).map(() => new Array(m).fill(0));
  let count = 0;
  function getDigitSum(number) {
    let sum = 0;
    while (number > 0) {
      sum += number % 10;
      number = (number / 10) >> 0; // 取整
    }
    return sum;
  }
  // 递归
  function movingCountCore(i, j) {
    if (
      i >= 0 &&
      i < n &&
      j >= 0 &&
      j < m &&
      getDigitSum(i) + getDigitSum(j) <= k &&
      !visited[i][j]
    ) {
      // 标记
      visited[i][j] = 1;
      count++;
      // 上下左右查找下一层
      movingCountCore(i - 1, j);
      movingCountCore(i, j - 1);
      movingCountCore(i, j + 1);
      movingCountCore(i + 1, j);
    }
  }
  movingCountCore(0, 0);
  return count;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch