489. Robot Room Cleaner

use backtrack to cover all cells
use visited to avoid re-cleaning a cell
direction para in backtrack() indicates the direction of the robot, but the actual direction of robot has to be controlled by calling methods of robot
when backtrack is done, restore the position and direction of the robot by calling methods of robot
once we finish a cell (either backtrack is completed or a wall blocks), the robot can always turn right
time/space complexity: O(N-M) N is number of cells and M is obstacles. each cell is visited only once since there is a set

class Solution:
    def cleanRoom(self, robot):
        """
        :type robot: Robot
        :rtype: None
        """
        DIR = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        def backtrack(row, col, direction):
            robot.clean()

            for i in range(4):
                new_dir = (direction + i) % 4
                new_row, new_col = row + DIR[new_dir][0], col + DIR[new_dir][1]
                # check before or inside backtrack? always prefer upfront check
                if (new_row, new_col) not in visited and robot.move():
                    visited.add((new_row, new_col))
                    backtrack(new_row, new_col, new_dir)

                    # back to original cell and direction before moving
                    robot.turnRight()
                    robot.turnRight()
                    robot.move()
                    robot.turnRight()
                    robot.turnRight()
                # change to the next direction no matter finishing backtrack or encountering wall
                # ensure robot direction aligns with new_dir in the next iteration and restores when leaving the loop
                robot.turnRight() # aligning with DIR, can change to turnLeft() if DIR = [(-1, 0), (0, -1), (1, 0), (0, 1)]

        visited = set([(0, 0)])
        backtrack(0, 0, 0)

489. Robot Room Cleaner - cocoder39/coco39_LC GitHub Wiki