这道题有一点难懂,它不像其它graph的题那样有一个array作为输入,而是需要robot具有自学习能力,慢慢探索地图,所以只有robot一个input。明白这个以后思路还是很直接的:
- 定义一个set存放已经访问过的位置
- dfs每一个位置,如果未访问过则清理该位置
- iterave四个方向,如果可以移动到下个位置,则dfs之,如果不行,转90度继续尝试 (在清理完之后要回到当前位置,方向也要相同)
var cleanRoom = function(robot) {
const set = new Set();
// direction: 0: N, 90: W, 180: E, 270: W
helper(robot, set, 0, 0, 0);
};
function helper(robot, set, x, y, dir) {
const code = `${x}->${y}`;
if (set.has(code)) {
return;
}
set.add(code);
robot.clean();
const nextDirs = [0, 90, 180, 270];
for (let i = 0; i < 4; i++) {
if (robot.move()) {
if (dir === 0) {
helper(robot, set, x-1, y, dir);
} else if (dir === 90) {
helper(robot, set, x, y-1, dir);
} else if (dir === 180) {
helper(robot, set, x+1, y, dir);
} else {
helper(robot, set, x, y+1, dir);
}
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnRight();
robot.turnRight();
}
dir += 90;
dir = dir % 360;
robot.turnRight();
}
}