The Robot Room Cleaner problem asks you to program a robot to clean an entire room using only the robot's limited movement and sensing APIs. The room is modeled as a grid, where some cells are open and some are blocked. The robot starts at an unknown location in the room, facing an arbitrary direction. You are given only access to the robot's interface:
move(): Moves the robot forward by one cell if possible; returns true if the next cell is open, false if blocked.turnLeft() and turnRight(): Rotates the robot 90 degrees left or right.clean(): Cleans the current cell.The robot has no prior knowledge of the room layout, its starting position, or its orientation. The goal is to clean all accessible cells in the room. You must ensure that:
Constraints: You can only use the robot's provided APIs. You do not know the room's dimensions or the robot's coordinates.
At first glance, this problem seems challenging because you have no direct access to the room grid or the robot's position. The only way to explore is by moving and sensing obstacles. A brute-force approach would be to try all possible moves, but this could lead to redundant cleaning and inefficient backtracking.
To solve this efficiently, we can think of the problem as exploring a maze using depth-first search (DFS). We need a way to remember which cells we've visited, even though we can't see the room. We can simulate coordinates relative to the starting point and use a visited set to keep track of cleaned cells.
The key insight is to treat the robot's starting position as (0, 0) and assign relative coordinates as the robot moves. Whenever the robot moves to a new cell, we record its relative position and avoid revisiting it. Whenever we finish exploring from a cell, we need to backtrack to the previous cell and restore the robot's orientation.
Here’s how we can design the solution step-by-step:
By following these steps, we ensure that each accessible cell is visited and cleaned exactly once, and the robot never gets lost or stuck.
Consider a simple 3x3 room:
1 1 1
1 0 1
1 1 1
Where 1 is open and 0 is blocked. Suppose the robot starts at the center (1, 1), which is blocked, but let's say it starts at (0, 0) facing up.
This process continues until all reachable cells are cleaned.
Brute-force:
The efficiency comes from marking visited cells and never re-exploring them.
The Robot Room Cleaner problem is a classic example of exploring an unknown environment with limited information. By simulating coordinates, tracking visited cells, and using DFS with careful backtracking, we ensure efficient and complete cleaning of all accessible cells. The elegance lies in handling the robot's orientation and position abstractly, allowing the algorithm to work for any room layout and starting position.
# """
# 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.
# */
#
# def turnLeft(self):
# /** Robot will stay in the same cell after calling turnLeft/turnRight. */
#
# def turnRight(self):
#
# def clean(self):
# /** Clean the current cell. */
# """
class Solution:
def cleanRoom(self, robot):
# Directions: up, right, down, left
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
visited = set()
def go_back():
robot.turnLeft()
robot.turnLeft()
robot.move()
robot.turnLeft()
robot.turnLeft()
def dfs(x, y, d):
visited.add((x, y))
robot.clean()
for i in range(4):
nd = (d + i) % 4
nx, ny = x + directions[nd][0], y + directions[nd][1]
if (nx, ny) not in visited:
if robot.move():
dfs(nx, ny, nd)
go_back()
robot.turnRight()
dfs(0, 0, 0)
/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* class Robot {
* public:
* // 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.
* bool move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* void turnLeft();
* void turnRight();
*
* // Clean the current cell.
* void clean();
* };
*/
class Solution {
public:
// Directions: up, right, down, left
int dirs[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
set> visited;
void goBack(Robot& robot) {
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
void dfs(Robot& robot, int x, int y, int d) {
visited.insert({x, y});
robot.clean();
for (int i = 0; i < 4; ++i) {
int nd = (d + i) % 4;
int nx = x + dirs[nd][0];
int ny = y + dirs[nd][1];
if (!visited.count({nx, ny})) {
if (robot.move()) {
dfs(robot, nx, ny, nd);
goBack(robot);
}
}
robot.turnRight();
}
}
void cleanRoom(Robot& robot) {
dfs(robot, 0, 0, 0);
}
};
/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* interface Robot {
* // 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.
* public boolean move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* public void turnLeft();
* public void turnRight();
*
* // Clean the current cell.
* public void clean();
* }
*/
class Solution {
int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
Set<String> visited = new HashSet<>();
private void goBack(Robot robot) {
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
private void dfs(Robot robot, int x, int y, int d) {
visited.add(x + "," + y);
robot.clean();
for (int i = 0; i < 4; ++i) {
int nd = (d + i) % 4;
int nx = x + dirs[nd][0];
int ny = y + dirs[nd][1];
String key = nx + "," + ny;
if (!visited.contains(key)) {
if (robot.move()) {
dfs(robot, nx, ny, nd);
goBack(robot);
}
}
robot.turnRight();
}
}
public void cleanRoom(Robot robot) {
dfs(robot, 0, 0, 0);
}
}
/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* function Robot() {
* @return {boolean} // true if next cell is open and robot moves into the cell.
* // false if next cell is obstacle and robot stays on the current cell.
* this.move = function() {};
*
* // Robot will stay on the same cell after calling turnLeft/turnRight.
* this.turnLeft = function() {};
* this.turnRight = function() {};
*
* // Clean the current cell.
* this.clean = function() {};
* }
*/
/**
* @param {Robot} robot
* @return {void}
*/
var cleanRoom = function(robot) {
// Directions: up, right, down, left
const dirs = [[-1,0],[0,1],[1,0],[0,-1]];
const visited = new Set();
function goBack() {
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
function dfs(x, y, d) {
visited.add(x + ',' + y);
robot.clean();
for (let i = 0; i < 4; ++i) {
const nd = (d + i) % 4;
const nx = x + dirs[nd][0];
const ny = y + dirs[nd][1];
const key = nx + ',' + ny;
if (!visited.has(key)) {
if (robot.move()) {
dfs(nx, ny, nd);
goBack();
}
}
robot.turnRight();
}
}
dfs(0, 0, 0);
};