DFS是否以任何顺序清洁网格上的每个房间？

Question

考虑将“机器人清洁器”放在建模为网格的房间中的问题。网格中的每个单元格都可以为空或阻塞，并且所有可访问的单元格都已连接，这意味着，无论其开始位置如何，所有空单元格都将由机器人accessible进行。

我们被告知机器人清洁器只能执行以下四个操作之一：

• robot.move()向前移动（如果下一个单元打开并且机器人moves进入该单元，则返回true；如果下一个单元是障碍物且当前单元上的机器人stays >>，则返回false。）
• [robot.turn_left()向左转（90度，不移动）
• [robot.turn_right()向右转（90度，不移动）
• robot.clean()清洁网格中的当前单元格

我们被要求设计一种用于机器人清理整个房间的算法。

---

我发现的这个问题的每个解决方案都考虑在顺时针或逆时针

方向（即所谓的围墙原理）上探索相邻的单元（当前正在访问的单元），相对于单元中机器人的当前方向（例如下面的Python示例）。为什么？

例如为什么常规DFS（然后以any顺序选择相邻的单元格（例如，尝试所有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()
考虑将“机器人清洁器”放在建模为网格的房间中的问题。网格中的每个单元格都可以为空或阻塞，并且所有可访问的单元格都已连接，这意味着所有空单元格都将是...

Answer 1

DFS将起作用，无论您使用什么顺序尝试相邻的单元格。但是，它并不是特别有效，因为它会花费大量时间回溯已探查过的单元。使用DFS，在每个“子”单元之后，您都必须重新输入已经访问过的父级。

使用不同的策略最多可以快一倍，而需要的移动次数仅为一半。但是，其他策略通常更复杂。