题目

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路

从第一个格开始走，进入递归

• 判断当前字符是否满足递归终止条件
• 递归终止条件：(1).行列越界 (2).行列值超出范围 (3).已经走过(需设定一个数组标识当前字符是否走过)
• 条件不满足，返回0，向上回溯。
• 若上面三个条件都满足，继续向下递归，返回四个方向的递归之和+1（当前节点）

下面是本算法的动画展示，可以点击机器人的运动范围动画 (opens new window)手动尝试。

代码

    function movingCount(threshold, rows, cols) {
      const flag = createArray(rows, cols);
      let count = 0;
      if (rows > 0 && cols > 0) {
        count = movingCountCore(0, 0, threshold, rows, cols, flag);
      }
      return count;
    }

    function movingCountCore(i, j, threshold, rows, cols, flag) {
      if (i < 0 || j < 0 || i >= rows || j >= cols) {
        return 0;
      }
      if (flag[i][j] || condition(i, j, threshold)) {
        flag[i][j] = true;
        return 0;
      }
      flag[i][j] = true;
      return 1 + movingCountCore(i - 1, j, threshold, rows, cols, flag) +
        movingCountCore(i + 1, j, threshold, rows, cols, flag) +
        movingCountCore(i, j - 1, threshold, rows, cols, flag) +
        movingCountCore(i, j + 1, threshold, rows, cols, flag);
    }

    /**
     * 判断是否符合条件
     */
    function condition(i, j, threshold) {
      let temp = i + '' + j;
      let sum = 0;
      for (var i = 0; i < temp.length; i++) {
        sum += temp.charAt(i) / 1;
      }
      return sum > threshold;
    }

    /**
     * 创建一个二维空数组
     */
    function createArray(rows, cols) {
      const result = new Array(rows) || [];
      for (let i = 0; i < rows; i++) {
        const arr = new Array(cols);
        for (let j = 0; j < cols; j++) {
          arr[j] = false;
        }
        result[i] = arr;
      }
      return result;
    }