考虑一个问题，一个“机器人清洁工”被放置在一个模拟为网格的房间上。网格中的每个单元都可以是空的或被阻塞的，并且所有可访问的单元都被连接起来，这意味着，无论机器人的起始位置如何，所有空单元都将被机器人访问。

我们被告知机器人清洁工只能采取以下四种行动之一：

• robots. mobile（）前进（如果下一个单元格打开并且机器人进入单元格，则返回true，如果下一个单元格是障碍物并且机器人停留在当前单元格上，则返回false。）
• 机器人。turn_left（）左转（90度，不动）
• 机器人。turn_right（）右转（90度，不动）
• robots. right（）清理网格中的当前单元格

我们被要求为机器人设计一个算法来清洁整个房间。

我发现这个问题的每个解决方案都考虑相对于细胞中机器人的当前方向（例如下面Python中的示例），以顺时针或逆时针方向探索相邻的细胞（当前访问的细胞）。为什么？

例如，为什么常规DFS（因此以任何顺序选择相邻单元格（例如尝试所有4个方向，例如上/下/右/左，而不管当前位置）在这里不起作用？

def clean_room(robot):

    def go_back():
        robot.turn_right()
        robot.turn_right()
        robot.move()
        robot.turn_right()
        robot.turn_right()

    def backtrack(cell = (0, 0), d = 0):
        visited.add(cell)
        robot.clean()

        # Always going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
        for i in range(4):
            new_d = (d + i) % 4
            new_cell = (cell[0] + directions[new_d][0], \
                        cell[1] + directions[new_d][1])

            if not new_cell in visited and robot.move():
                backtrack(new_cell, new_d)
                go_back()
            # turn the robot following chosen direction : clockwise
            robot.turn_right()

    # Going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = set()
    backtrack()