题目

题目来源：力扣（LeetCode）

地上有一个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. 我们将行坐标和列坐标数位之和大于 k 的格子看作障碍物，然后用广度优先搜索它。
  2. 然后我们计算一个数的数位之和。对数 x 每次对 10 取余，就能知道数 x 的个位数是多少，然后再将 x 除 10，这个操作等价 于将 x 的十进制数向右移一位，删除个位数（类似于二进制中的 >> 右移运算符），不断重复直到 x 为 0 时结束。
  3. 我们在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索。
  1. /**
  2.  * @param {number} m
  3.  * @param {number} n
  4.  * @param {number} k
  5.  * @return {number}
  6.  */
  7. var movingCount = function (m, n, k) {
  8.   // 计算一个数的数位之和
  9.   // 对数 x 每次对 10 取余，就能知道数 x 的个位数是多少，然后再将 x 除 10，这个操作等价于将 x 的十进制数向右移一位，删除个位数（类似于二进制中的 >> 右移运算符），不断重复直到 x 为 0 时结束
  10.   const getSum =(num) => {
  11.     let res = 0;
  12.     while(num) {
  13.       res += num % 10;
  14.       num = Math.floor(num/10);
  15.     }
  16.     return res;
  17.   }
  19.   // 方向数组
  20.   // 在搜索的过程中搜索方向可以缩减为向右和向下，而不必再向上和向左进行搜索
  21.   const directions = [
  22.     [0, 1], // 右
  23.     [1, 0]  // 下
  24.   ]
  26.   // 已经走过的坐标
  27.   let set = new Set(['0,0']);
  28.   // 将遍历的坐标队列，题意要求从[0,0]开始走
  29.   let queue = [[0, 0]];
  30.   // 遍历队列中的坐标
  31.   while (queue.length) {
  32.     // 移除队首坐标
  33.     let [x, y] = queue.shift();
  34.     // 遍历方向
  35.     for (let i = 0; i < 2; i++) {
  36.       let offsetX = x + directions[i][0];
  37.       let offsetY = y + directions[i][1];
  38.       // 临界值判断
  39.       if (offsetX < 0 || offsetX >= m || offsetY < 0 || offsetY >= n ||
  40.         getSum(offsetX) + getSum(offsetY) > k || set.has(`${offsetX},${offsetY}`)) {
  41.         continue;
  42.       }
  43.       // 走过的格子就不再纳入统计
  44.       set.add(`${offsetX},${offsetY}`);
  45.       // 将该坐标加入队列（因为这个坐标的右边和下边没有走过，需要纳入下次的遍历）
  46.       queue.push([offsetX, offsetY]);
  47.     }
  48.   }
  49.   // 走过坐标的个数就是可以到达的格子数
  50.   return set.size;
  51. }