扫地机器人

Submission

运行时间: 39 ms

内存: 16.9 MB

# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
#class Robot:
#    def move(self):
#        """
#        Returns true if the cell in front is open and robot moves into the cell.
#        Returns false if the cell in front is blocked and robot stays in the current cell.
#        :rtype bool
#        """
#
#    def turnLeft(self):
#        """
#        Robot will stay in the same cell after calling turnLeft/turnRight.
#        Each turn will be 90 degrees.
#        :rtype void
#        """
#
#    def turnRight(self):
#        """
#        Robot will stay in the same cell after calling turnLeft/turnRight.
#        Each turn will be 90 degrees.
#        :rtype void
#        """
#
#    def clean(self):
#        """
#        Clean the current cell.
#        :rtype void
#        """

class Solution:
    def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """

        def go_back():
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()
            return

        def dfs(i, j, d):
            robot.clean()
            visit.add((i, j))
            for k in range(len(directions)):
                new_d = (d + k) % 4
                dx, dy = directions[new_d][0], directions[new_d][1]
                x, y = i + dx, j + dy
                if (x, y) not in visit and robot.move():
                    dfs(x, y, new_d)
                    go_back()
                robot.turnRight()
            return

        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        visit = set()
        dfs(0, 0, 0)
        return

Explain

这个题解使用深度优先搜索 (DFS) 的方式来遍历并清扫房间。机器人从初始位置 (0, 0) 开始，朝向初始方向。在每个位置，机器人先清扫当前格子，然后依次尝试向右转并前进到下一个格子，重复 DFS 过程。如果四个方向都无法前进（可能是因为已经清扫过或者被障碍物阻挡），则返回上一个位置。通过递归的方式，机器人能够遍历整个房间的所有可达格子。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """

        def go_back():
            # 机器人向后退一步，并恢复原始朝向
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnRight()
            robot.turnRight()
            return

        def dfs(i, j, d):
            # 清扫当前格子
            robot.clean()
            # 将当前格子标记为已访问
            visit.add((i, j))
            # 依次尝试四个方向
            for k in range(len(directions)):
                # 计算下一个方向
                new_d = (d + k) % 4
                # 计算下一个格子的坐标
                dx, dy = directions[new_d][0], directions[new_d][1]
                x, y = i + dx, j + dy
                # 如果下一个格子没有被访问过，且可以前进
                if (x, y) not in visit and robot.move():
                    # 递归清扫下一个格子
                    dfs(x, y, new_d)
                    # 返回当前格子
                    go_back()
                # 向右转，尝试下一个方向
                robot.turnRight()
            return

        # 四个方向的坐标变化
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        # 记录已访问过的格子
        visit = set()
        # 从起始位置开始清扫
        dfs(0, 0, 0)
        return

Explore

在题解中，判断四个方向都无法前进的条件是基于每次尝试移动到新格子时的结果。对于每个方向，机器人首先尝试向该方向移动（robot.move()）。如果移动成功，说明该方向可以前进，并且机器人将继续递归调用dfs函数来继续清扫新的格子。如果robot.move()返回False，这意味着这个方向有障碍物或者是已经清扫过的格子边界。当四个方向的robot.move()都返回False时，说明四个方向都无法前进。

是的，使用递归方式实现DFS在非常大的房间中可能会导致栈溢出，因为递归的深度可能会非常深，尤其是在房间复杂或者房间尺寸非常大时。每一层的递归调用都会占用调用栈上的空间，如果递归层数过多，将超出栈的容量限制。在实际应用中，可以考虑使用迭代版本的DFS或其他避免深层递归的策略，例如使用显式的栈来管理状态。

在算法中，使用一个集合（set）来存储已经访问过的格子的坐标。在每次清扫一个新的格子之前，会先检查这个格子的坐标是否已经存在于集合中。如果不存在，机器人会清扫这个格子，并将其坐标添加到集合中。这样可以确保每个格子只被访问和清扫一次，防止重复清扫。

是的，每次机器人向右转后，都需要再次调用robot.move()来验证该方向是否可前进。这是因为机器人的当前朝向已经改变，需要重新检查新的朝向是否有障碍。如果robot.move()返回True，则继续递归探索新的格子；如果返回False，则继续向右转，尝试下一个方向。这个过程确保了机器人能够检查所有可能的方向。