How to solve LeetCode 489 (Robot Room Cleaner)?

This page provides optimized solutions for LeetCode problem 489 (Robot Room Cleaner) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 489: Robot Room Cleaner Solution

Problem Description

Explanation

To solve the "Robot Room Cleaner" problem, we can use backtracking along with a set to keep track of visited cells. We can define the robot's movements (up, down, left, right) and recursively explore all possible directions while cleaning the cells.

Algorithmic Idea:

Define the movements of the robot (up, down, left, right) and a helper function to move the robot in each direction.
Use backtracking to explore all possible directions while cleaning cells and marking visited cells.
Recursively move the robot in all directions while ensuring it does not move to a visited or obstacle cell.

Time Complexity:

The time complexity of this algorithm is O(4^n), where n is the number of cells to be cleaned.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of cells to be cleaned.

Solutions

class Solution {
    public void cleanRoom(Robot robot) {
        Set<String> visited = new HashSet<>();
        backtrack(robot, visited, 0, 0, 0);
    }
    
    private void backtrack(Robot robot, Set<String> visited, int x, int y, int direction) {
        String key = x + ":" + y;
        if (visited.contains(key)) return;
        
        robot.clean();
        visited.add(key);
        
        for (int i = 0; i < 4; i++) {
            if (robot.move()) {
                int newX = x, newY = y;
                switch (direction) {
                    case 0: newY--; break;
                    case 90: newX++; break;
                    case 180: newY++; break;
                    case 270: newX--; break;
                }
                backtrack(robot, visited, newX, newY, direction);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
            direction += 90;
            direction %= 360;
        }
    }
}