Robot Room Cleaner

XXX.Robot Room Cleaner

Simulation

Backtracking

Problem Statement:

A robot is located in a grid and can move in four cardinal directions (up, down, left, right). Some cells are blocked, and the robot cannot enter them. Implement a function to clean the entire accessible area using the robot's API. The robot's movements include move(), turnLeft(), turnRight(), and clean().

Algorithm:

1. Use depth-first search (DFS) to navigate and clean the grid.
2. Track visited cells using a set to avoid cleaning the same cell multiple times.
3. For each direction:
   • Calculate the new coordinates based on the current direction.
   • Move the robot forward if the cell is unvisited and accessible.
   • Recursively clean the new cell and then backtrack to the previous position.
4. Backtrack by turning the robot around, moving it back to the previous cell, and restoring its original direction.

Complexity:

Time: O(n), where n is the number of accessible cells in the grid | Space: O(n) for the visited set and recursion stack.

Java Implementation:

public static final int[][] DIRS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public void cleanRoom(Robot robot) {
    // Start cleaning from the initial position (0, 0) facing north (direction 0)
    clean(robot, 0, 0, 0, new HashSet<>());
}

private void clean(Robot robot, int x, int y, int curDirection, Set cleaned) {
    // Clean the current cell
    robot.clean();
    cleaned.add(x + " " + y);

    // Try all 4 directions from the current position
    for (int i = 0; i < 4; i++) {
        // Calculate the next cell's coordinates
        int nx = x + DIRS[curDirection][0];
        int ny = y + DIRS[curDirection][1];

        // Move to the next cell if it hasn't been cleaned and is accessible
        if (!cleaned.contains(nx + " " + ny) && robot.move()) {
            clean(robot, nx, ny, curDirection, cleaned);
            goBack(robot); // Return to the previous cell after cleaning
        }

        // Turn the robot 90 degrees to the right and update the direction
        robot.turnRight();
        curDirection = (curDirection + 1) % 4;
    }
}

private void goBack(Robot robot) {
    // Turn the robot around to face the previous cell
    robot.turnRight();
    robot.turnRight();
    robot.move(); // Move back to the previous cell
    robot.turnRight();
    robot.turnRight(); // Restore the original direction
}
                

Python Implementation:

DIRS = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def cleanRoom(robot):
    def clean(x, y, curDirection, cleaned):
        # Clean the current cell
        robot.clean()
        cleaned.add((x, y))

        # Try all 4 directions
        for i in range(4):
            nx, ny = x + DIRS[curDirection][0], y + DIRS[curDirection][1]
            if (nx, ny) not in cleaned and robot.move():
                clean(nx, ny, curDirection, cleaned)
                goBack()
            # Turn right and update direction
            robot.turnRight()
            curDirection = (curDirection + 1) % 4

    def goBack():
        robot.turnRight()
        robot.turnRight()
        robot.move()
        robot.turnRight()
        robot.turnRight()

    clean(0, 0, 0, set())
                

C++ Implementation:

class Solution {
    vector> DIRS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public:
    void cleanRoom(Robot& robot) {
        unordered_set cleaned;
        clean(robot, 0, 0, 0, cleaned);
    }

    void clean(Robot& robot, int x, int y, int curDirection, unordered_set& cleaned) {
        // Clean the current cell
        robot.clean();
        cleaned.insert(to_string(x) + " " + to_string(y));

        for (int i = 0; i < 4; i++) {
            int nx = x + DIRS[curDirection][0];
            int ny = y + DIRS[curDirection][1];

            if (!cleaned.count(to_string(nx) + " " + to_string(ny)) && robot.move()) {
                clean(robot, nx, ny, curDirection, cleaned);
                goBack(robot);
            }
            robot.turnRight();
            curDirection = (curDirection + 1) % 4;
        }
    }

    void goBack(Robot& robot) {
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }
};