题目

地上有一个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(当前节点)

下面是本算法的动画展示,可以点击机器人的运动范围动画手动尝试。

foo

代码

    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;
    }
Last Updated: 8/30/2019, 11:32:31 AM