Leetcode 865 Solution

# """
# 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
        """
        visited = set()

        def dfs(i, j, direction):
            nonlocal robot
            nonlocal visited

            key = (i, j)
            if key in visited:
                return
            visited.add(key)

            robot.clean()

            new_direction = direction
            for _ in range(4):
                if robot.move():
                    if new_direction == 0:
                        dfs(i - 1, j, new_direction)
                    elif new_direction == 1:
                        dfs(i, j + 1, new_direction)
                    elif new_direction == 2:
                        dfs(i + 1, j, new_direction)
                    elif new_direction == 3:
                        dfs(i, j - 1, new_direction)
                    else:
                        raise Exception("Unexpected direction {}".format(new_direction))

                    robot.turnLeft()
                    robot.turnLeft()
                    robot.move()
                    robot.turnLeft()
                    robot.turnLeft()

                robot.turnRight()
                new_direction = (new_direction + 1) % 4

        dfs(0, 0, 0)