剑指 Offer 13. 机器人的运动范围

[Tcdian]

剑指 Offer 13. 机器人的运动范围

地上有一个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。请问该机器人能够到达多少个格子？

Example 1

输入：m = 2, n = 3, k = 1
输出：3

Example 2

输入：m = 3, n = 1, k = 0
输出：1

Note

• 1 <= n,m <= 100
• 0 <= k <= 20

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
    const queue = [[0, 0]];
    const direction = [0, 1, 0];
    const visited = new Set();
    let result = 0;
    while(queue.length !== 0) {
        const p = queue.shift();
        result += 1;
        for (let i = 0; i < 2; i++) {
            const positionX = p[0] + direction[i];
            const positionY = p[1] + direction[i + 1];
            if (positionX >= 0 && positionX < m && positionY >= 0 && positionY < n) {
                const digitSum = positionX % 10 + Math.floor(positionX / 10)
                    + positionY % 10 + Math.floor(positionY / 10);
                if (digitSum <= k && !visited.has(positionX * 100 + positionY)) {
                    queue.push([positionX, positionY]);
                    visited.add(positionX * 100 + positionY);
                }
            }
        }
    }
    return result
};