这道题有一点难懂,它不像其它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();
    }
}

results matching ""

    No results matching ""