LC 0489 [H] Robot Room Cleaner - ALawliet/algorithms GitHub Wiki

move forward: move; orientation x (^)
move right: turnRight, move; orientation (x + 1) % 4 (>)
move backward: turnRight, turnRight, move; orientation (x + 2) % 4 (v)
move left: turnRight, turnRight, turnRight, move; orientation (x + 3) % 4 (<)

this new_d = (d + i) % 4 is required because it is not a regular DFS, it is a DFS that uses right-hand rule so we always turn to the next right/clockwise, the order is important

# going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

class Solution(object):       
    def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """
        def go_back():
            robot.turnRight() ; robot.turnRight() ; robot.move() # reset position
            robot.turnRight() ; robot.turnRight() # reset direction
            
        def backtrack(rc, d):
            visited.add(rc)
            robot.clean()

            for i in range(4):
                nd = (d + i) % 4
                nrc = (rc[0] + DIRS[nd][0], rc[1] + DIRS[nd][1])
                
                if nrc not in visited and robot.move():
                    backtrack(nrc, nd)
                    go_back()

                # could not move() by this point: there is an obstacle right in front - turn the robot following chosen direction : clockwise
                robot.turnRight()
    
        visited = set()
        backtrack((0,0), 0)

# """
# 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):
        def goBack():
            robot.turnLeft(); robot.turnLeft()
            robot.move() # previous position
            robot.turnLeft(); robot.turnLeft() # previous direction
        
        def dfs(x, y, dx, dy):
            # 1, Clean current
            path.add((x, y))
            robot.clean()

            # 2, Clean next
            for _ in range(4):
                if (x + dx, y + dy) not in path and robot.move():
                    dfs(x + dx, y + dy, dx, dy)
                robot.turnLeft()
                dx, dy = -dy, dx
                # 0,1 => -1,0
                # -1,0 => 1,0
                # 1,0 => 0,1
                # 0,1 => 0,-1

            # 3, Back to previous position and direction
            goBack()

        path = set()
        dfs(0, 0, 0, 1)