题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
分析
对于每个到(x,y)的机器人，有四种移动可能，上下左右，即：(x+1,y)，(x-1,y)，(x,y-1)，(x,y+1)；
决定该位置是否合法要检查这么几个方面：
- x、y坐标不能超出rows和cols的界限
- x、y的坐标数位之和不能大于k
代码实现
function movingCount(k, rows, cols) { var flags = []; for(var i = 0;i < rows;i++) { flags.push([]); for(var j = 0;j < cols;j++) { flags[i].push(0); } } return steps(0,0,rows,cols,flags, k); } function steps(x, y, rows, cols, flags, k){ if(x <0 || x >= rows || y < 0 || y >= cols || flags[x][y] === 1 || (bitSum(x) + bitSum(y) > k) ) return 0; flags[x][y] = 1; return steps(x-1, y, rows, cols, flags, k) + steps(x+1, y, rows, cols, flags, k) + steps(x, y-1, rows, cols, flags, k) + steps(x, y+1, rows, cols, flags, k) + 1; } function bitSum(n){ var sum = 0; while(n >= 1){ sum += n%10; n = Math.floor(n/10); } return sum; }
