489. Robot Room Cleaner

# """
# 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):
        """
        tc O(N-M)  sc O(N-M)  N:  total cells M: number of obstacles 
        """
        dirs = [(-1,0),(0,1),(1,0),(0,-1)] # turn robot clockwise
        seen = set()
        def dfs(robot, x,y,cur_dir):
            seen.add((x,y))
            robot.clean()
            for k in range(4):
                next_dir = (k+cur_dir)%4
                nx = x + dirs[next_dir][0]
                ny = y + dirs[next_dir][1]
                if (nx,ny) not in seen and robot.move():
                    dfs(robot, nx, ny, next_dir)
                    self.go_back(robot)  
                robot.turnRight()
        dfs(robot, 0, 0, 0) # assuming start pos is (0,0), start direction is 0  (can be set to any )
    def go_back(self,robot):
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()