通过率 52.5%
题目描述：
地上有一个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
思路：
1. 深搜，有三个注意点：
- 机器人的前进方向：虽然题中说机器人东南西北四个方向都能走，不过就得出答案而言，考虑东和南两个方向就行了
- 标记走过的格子：用set记录走过的格子，这里一开始我将坐标以[i, j]数组形式存进set了，但是这样set记录的就是数组对象在内存中的地址，是无法正确记录走过的格子的，还是看了官网中Gatsby的题解之后才想到可以将坐标以字符串的形式存储set.add(`${i}, ${j}`)
- 求坐标数位和：抽成一个函数，随时调用，我一直是用常规法循环求余，题解中用库函数求数位和的想法我之前也是没有想到的，不是捧高踩低，权当多了解一些解法
2. 广搜
我一般能用深搜的就不用广搜，两者原理都差不多，不过广搜要用到队列，这里也写写巩固一下
代码：
1. 深搜
1 /*JavaScript*/ 2 /** 3 * @param {number} m 4 * @param {number} n 5 * @param {number} k 6 * @return {number} 7 */ 8 // 求数位和 9 var getBitSum = function(x) { 10 let sum = 0 11 while(x) { 12 sum += x % 10 13 x = Math.floor(x / 10) 14 } 15 return sum 16 // 利用库函数 17 // return x.toString().split(‘‘).reduce((ans, cur) => Number(ans) + Number(cur), 0) 18 } 19 // 深搜 20 var dfs = function(m, n, i, j, k, set) { 21 if(i < 0 || j < 0 || i >= m || j >= n || set.has(`${i}, ${j}`) || getBitSum(i) + getBitSum(j) > k) return 0 22 set.add(`${i}, ${j}`) 23 return 1 + dfs(m, n, i, j+1, k, set) + dfs(m, n, i+1, j, k, set) 24 } 25 26 var movingCount = function(m, n, k) { 27 const set = new Set() 28 return dfs(m, n, 0, 0, k, set) 29 };
2. 广搜
1 /*JavaScript*/ 2 /** 3 * @param {number} m 4 * @param {number} n 5 * @param {number} k 6 * @return {number} 7 */ 8 // 求数位和 9 var getBitSum = function(x) { 10 let sum = 0 11 while(x) { 12 sum += x % 10 13 x = Math.floor(x / 10) 14 } 15 return sum 16 // 利用库函数 17 // return x.toString().split(‘‘).reduce((ans, cur) => Number(ans) + Number(cur), 0) 18 } 19 // 广搜 20 var movingCount = function(m, n, k) { 21 const set = new Set() 22 const que = new Array() 23 que.push([0, 0]) 24 while(que.length) { 25 let [i, j] = que.shift() //数组的解构赋值 26 if(i < 0 || j < 0 || i >= m || j >= n || set.has(`${i}, ${j}`) || getBitSum(i) + getBitSum(j) > k) continue 27 set.add(`${i}, ${j}`) 28 que.push([i, j+1], [i+1, j]) 29 } 30 return set.size 31 };