题目描述

地上有一个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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这里练习下bfs，dfs就不写了

  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.   let queue = [{i: 0, j: 0}];
  9.   let visit = new Array(n * m).fill(false);
  10.   let count = 0;
  12.     // 判定该节点是否满足条件
  13.   function judge(i, j) {
  14.     if (i >= m || j >= n) return false;
  15.     let sum = 0;
  16.     i = i.toString().split('');
  17.     j = j.toString().split('');
  18.     i.forEach(item => {
  19.       sum += item * 1;
  20.     });
  21.     j.forEach(item => {
  22.       sum += item * 1;
  23.     })
  24.     // console.log(`Sum: ${sum}`);
  25.     return sum <= k;
  26.   }
  28.   // 用队列思想
  29.   while (queue.length) {
  30.     // 先取出要处理的节点
  31.     let item = queue.shift();
  32.     let {i, j} = item;
  33.     // 不满足条件
  34.     if (visit[i * n + j] || !judge(i, j)) {
  35.       continue;
  36.     }
  37.     // console.log(`${i},${j},${visit[i * n + j]}`);
  38.     // 作标记
  39.     visit[i * n + j] = true;
  40.     // 数量+1
  41.     count++;
  42.     // 把两个方向的节点加入队列中
  43.     queue.push({i: i + 1, j});
  44.     queue.push({i, j: j + 1});
  45.   }
  47.   return count;
  48. };