分析
bfs+set
Code
/**
* @param {number} threshold
* @param {number} rows
* @param {number} cols
* @return {number}
*/
var movingCount = function(threshold, rows, cols) {
if(rows === 0 || cols === 0) return 0; //特判
function getSum(num){
let ans = 0;
while(num){
ans += num % 10;
num = Math.floor(num / 10); // 53 /3 ==> 5
}
return ans;
}
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
//用set保存已经走过的坐标
let set = new Set(['0,0']);
//bfs
const queue = [[0,0]];
let res = 0;
while(queue.length > 0){
//弹出队头
const [x, y] = queue.shift();
//四个方向遍历
for(let i = 0; i < 4; i ++){
let a = x + dx[i];
let b = y + dy[i];
if (a < 0 || a >= rows || b < 0 || b >= cols || getSum(a) + getSum(b) > threshold || set.has(`${a},${b}`)) {
continue;
}
res += (getSum(a) + getSum(b));
set.add(`${a},${b}`);
queue.push([a, b]);
}
}
return set.size;
};