Problem statement

https://leetcode.com/problems/robot-room-cleaner/

Complexity

Time complexity is O(E+V) = O(V), where V is number of vertexes in our graph, that is number of empty cells. However due to all rotations and backtracking constant will be high, something like O(10V). Space complexity is O(V) to keep all visited nodes.

Code 1

class Solution:
    def cleanRoom(self, robot):
        visited = set()
        def dfs(x, y, dx, dy):
            robot.clean()
            visited.add((x, y))

            for _ in range(4):
                if (x + dx, y + dy) not in visited and robot.move():
                    dfs(x + dx, y + dy, dx, dy)
                robot.turnRight()
                dx, dy = -dy, dx

            for _ in range(2): robot.turnRight()
            robot.move()
            for _ in range(2): robot.turnRight()

        dfs(0, 0, 0, 1)

Code 2

Alternative way is to use for direction one number and increase it after each dfs 0 -> 1 -> 2 -> 3 -> 0 -> ...

class Solution:
    def cleanRoom(self, robot):
        visited = set()
        dirs = [[0,1], [-1,0], [0,-1], [1,0]]
		
        def dfs(x, y, dr):
            robot.clean()
            visited.add((x, y))
			
            for i in range(4):
                 cur = (i + dr)%4
                 newX, newY = x + dirs[cur][0], y + dirs[cur][1]
                 if (newX, newY) not in visited and robot.move():
                     dfs(newX, newY, cur)
                 robot.turnRight()

            for _ in range(2): robot.turnRight()
            robot.move()
            for _ in range(2): robot.turnRight()
                     
        dfs(0, 0, 0)