LCR130.衣橱整理

链接：LCR130.衣橱整理
难度：Medium
标签：深度优先搜索、广度优先搜索、动态规划
简介：地上有一个 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 - javascript

• 编辑时间：2020-04-08
• 执行用时：92ms
• 内存消耗：37.6MB
• 编程语言：javascript
• 解法介绍：广度优先搜索，从 0，0 开始依次向左下搜索。

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
  const comp = num => (num < 10 ? num : (num % 10) + Math.floor(num / 10));
  const nowComp = (num1, num2) => comp(num1) + comp(num2);
  let result = 0;
  const find = [[0, 0]],
    finded = {};
  while (find.length !== 0) {
    const [row, col] = find.shift();
    if (finded[`${row}:${col}`]) continue;
    if (col >= n || row >= m) continue;
    result++;
    finded[`${row}:${col}`] = true;
    if (nowComp(row, col + 1) <= k) find.push([row, col + 1]);
    if (nowComp(row + 1, col) <= k) find.push([row + 1, col]);
  }
  return result;
};