題目描述：

地上有一個m行和n列的方格。一個機(jī)器人從坐標(biāo)0,0的格子開始移動，每一次只能向左，右，上，下四個方向移動一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時，機(jī)器人能夠進(jìn)入方格（35,37），因為3+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因為3+5+3+8 = 19。請問該機(jī)器人能夠達(dá)到多少個格子？

示例1

輸入

5,10,10

返回值

21

1、遞歸的方式實現(xiàn)

/**
 * 1、核心思路是機(jī)器人從（0，0）坐標(biāo)開始走,走成功一步就標(biāo)記為true, 遞歸當(dāng)前位置上下左右的點(diǎn), 返回 1 + 4個方向的值
 * 2、遞歸時判斷當(dāng)前位置可達(dá)的標(biāo)準(zhǔn)
 * 1）當(dāng)前位置在矩陣內(nèi) r < 0 || r >= rows || c < 0 || c >= cols
 * 2）當(dāng)前位置未被訪問過 dp[r][c]
 * 3）當(dāng)前位置坐標(biāo)的數(shù)位之和大于limit
 */
function movingCount(threshold, rows, cols) {
    // write code here
    // 創(chuàng)建一個二維數(shù)組
    let dp = Array.from({
        length: rows
    }, x => Array.from({
        length: cols
    }, y => 0));
    return countAll(threshold, rows, cols, 0, 0, dp)
}
// 計算
function countAll(limit, rows, cols, r, c, dp) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || dp[r][c] || stepNum(r + '' + c) > limit) return 0;
    dp[r][c] = true
    // console.log(dp, "DP")
    return countAll(limit, rows, cols, r - 1, c, dp) +
        countAll(limit, rows, cols, r, c - 1, dp) +
        countAll(limit, rows, cols, r + 1, c, dp) +
        countAll(limit, rows, cols, r, c + 1, dp) + 1;
}
// 計算該位置坐標(biāo)的數(shù)位之和
function stepNum(str) {
    return str.split('').reduce(function (prev, curr, idx, arr) {
        return parseInt(prev) + parseInt(curr);
    });
}