Robot Room Cleaner
Robot Room Cleaner is a hard recursion & backtracking problem solved with the 2d matrix backtracking pattern.
The best approach, optimal (spiral backtracking dfs), runs in O(N) time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (dfs that re-aims before every move) up.
Problem
A cleaning robot is placed somewhere in a room laid out as a grid of cells, where each cell is either open or a wall. You do not know the layout, the grid size or where the robot starts. All you can do is control the robot through this interface:
move(): try to step one cell forward. Returnstrueand moves if the cell ahead is open; returnsfalseand stays put if it is a wall or the edge of the room.turnLeft()/turnRight(): rotate 90 degrees in place.clean(): clean the current cell.
The robot starts facing up. Implement cleanRoom(robot) so that the robot cleans every open cell reachable from its starting cell.
Examples
Example 1
- Input
room = [[1, 1, 0], [0, 1, 1], [1, 1, 1]], row = 1, col = 1- Output
all 7 open cells cleaned- Why
- The robot starts in the centre facing up. It cannot see the grid; it has to discover the two walls (value 0) by bumping into them and still visit every open cell.
Example 2
- Input
room = [[1]], row = 0, col = 0- Output
all 1 open cells cleaned- Why
- Every move fails, so cleaning the starting cell is enough.
Example 3
- Input
room = [[1, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1]], row = 2, col = 0- Output
all 9 open cells cleaned- Why
- The open cells form a corridor that winds back on itself; the robot must follow it to the end and back.
Constraints
1 <= rows, cols <= 100, each cell is0(wall) or1(open).- The robot starts on an open cell, facing up.
- All open cells are connected to the start, and everything outside the grid counts as wall.
- Your code never sees the grid, the size or the starting position; it may only call the four robot methods.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DFS that re-aims before every move) | O(N · 4) | O(N) |
| Optimal (spiral backtracking DFS) | O(N) | O(N) |
1Brute force (DFS that re-aims before every move)
O(N · 4)N = open cells. Each cell is entered once, and each of its four directions costs at most a few turns and a move.O(N)The visited set and the recursion depth are both up to N.Track the robot's absolute facing (0 = up, 1 = right, 2 = down, 3 = left). From each cell, try the four absolute directions in order: turn right until the robot faces that direction, and if the neighbour is unvisited and move() succeeds, recurse. To return, face the opposite direction and move back. This is correct but spends extra turns re-aiming the robot from scratch for each direction.
- dfs(r, c): clean, mark (r, c) visited.
- For d in 0..3: turn right until facing == d. If (r + dr[d], c + dc[d]) is unvisited and move() succeeds: dfs(neighbour), then face (d + 2) % 4 and move() back.
- Start with dfs(0, 0) and facing = 0.
class Solution {
private final int[] dr = { -1, 0, 1, 0 };
private final int[] dc = { 0, 1, 0, -1 };
private final Set<String> seen = new HashSet<>();
private int facing = 0;
private Robot robot;
public void cleanRoom(Robot robot) {
this.robot = robot;
dfs(0, 0);
}
private void face(int d) {
while (facing != d) {
robot.turnRight();
facing = (facing + 1) % 4;
}
}
private void dfs(int r, int c) {
robot.clean();
seen.add(r + "," + c);
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
face(d);
if (!seen.contains(nr + "," + nc) && robot.move()) {
dfs(nr, nc);
face((d + 2) % 4);
robot.move();
}
}
}
}class Solution:
def cleanRoom(self, robot) -> None:
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
seen = set()
facing = [0]
def face(d: int) -> None:
while facing[0] != d:
robot.turnRight()
facing[0] = (facing[0] + 1) % 4
def dfs(r: int, c: int) -> None:
robot.clean()
seen.add((r, c))
for d in range(4):
nr, nc = r + dr[d], c + dc[d]
face(d)
if (nr, nc) not in seen and robot.move():
dfs(nr, nc)
face((d + 2) % 4)
robot.move()
dfs(0, 0)class Solution {
public:
void cleanRoom(Robot& robot) {
rb = &robot;
dfs(0, 0);
}
private:
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
set<pair<int, int>> seen;
int facing = 0;
Robot* rb = nullptr;
void face(int d) {
while (facing != d) {
rb->turnRight();
facing = (facing + 1) % 4;
}
}
void dfs(int r, int c) {
rb->clean();
seen.insert({r, c});
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
face(d);
if (!seen.count({nr, nc}) && rb->move()) {
dfs(nr, nc);
face((d + 2) % 4);
rb->move();
}
}
}
};function cleanRoom(robot) {
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const seen = new Set();
let facing = 0;
const face = (d) => {
while (facing !== d) {
robot.turnRight();
facing = (facing + 1) % 4;
}
};
const dfs = (r, c) => {
robot.clean();
seen.add(r + "," + c);
for (let d = 0; d < 4; d++) {
const nr = r + dr[d], nc = c + dc[d];
face(d);
if (!seen.has(nr + "," + nc) && robot.move()) {
dfs(nr, nc);
face((d + 2) % 4);
robot.move();
}
}
};
dfs(0, 0);
}2Optimal (spiral backtracking DFS)
O(N)N = open cells. Each cell is entered once and each of its four sides is probed once, with a constant number of robot calls per probe.O(N)The visited set and the recursion depth are both up to N.Pass the current facing into the DFS. From a cell facing d, try directions d, d+1, d+2, d+3 (clockwise) by turning right once after each try. After exploring a neighbour, goBack returns the robot to the cell with the same facing it had before the move (turn around, step, turn around). Because the robot ends each try facing the direction it tried, one right turn moves it to the next direction, and after four tries it faces d again, exactly as the caller expects.
- dfs(r, c, d): clean, mark (r, c) visited.
- For k in 0..3: nd = (d + k) % 4; if (r + dr[nd], c + dc[nd]) is unvisited and move() succeeds: dfs(neighbour, nd), then goBack().
- turnRight() after every try, so the robot faces the next clockwise direction.
- goBack(): turnRight, turnRight, move, turnRight, turnRight.
class Solution {
private final int[] dr = { -1, 0, 1, 0 };
private final int[] dc = { 0, 1, 0, -1 };
private final Set<String> seen = new HashSet<>();
private Robot robot;
public void cleanRoom(Robot robot) {
this.robot = robot;
dfs(0, 0, 0);
}
private void goBack() {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
private void dfs(int r, int c, int d) {
robot.clean();
seen.add(r + "," + c);
for (int k = 0; k < 4; k++) {
int nd = (d + k) % 4;
int nr = r + dr[nd], nc = c + dc[nd];
if (!seen.contains(nr + "," + nc) && robot.move()) {
dfs(nr, nc, nd);
goBack();
}
robot.turnRight();
}
}
}class Solution:
def cleanRoom(self, robot) -> None:
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
seen = set()
def go_back() -> None:
robot.turnRight()
robot.turnRight()
robot.move()
robot.turnRight()
robot.turnRight()
def dfs(r: int, c: int, d: int) -> None:
robot.clean()
seen.add((r, c))
for k in range(4):
nd = (d + k) % 4
nr, nc = r + dr[nd], c + dc[nd]
if (nr, nc) not in seen and robot.move():
dfs(nr, nc, nd)
go_back()
robot.turnRight()
dfs(0, 0, 0)class Solution {
public:
void cleanRoom(Robot& robot) {
rb = &robot;
dfs(0, 0, 0);
}
private:
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
set<pair<int, int>> seen;
Robot* rb = nullptr;
void goBack() {
rb->turnRight();
rb->turnRight();
rb->move();
rb->turnRight();
rb->turnRight();
}
void dfs(int r, int c, int d) {
rb->clean();
seen.insert({r, c});
for (int k = 0; k < 4; k++) {
int nd = (d + k) % 4;
int nr = r + dr[nd], nc = c + dc[nd];
if (!seen.count({nr, nc}) && rb->move()) {
dfs(nr, nc, nd);
goBack();
}
rb->turnRight();
}
}
};function cleanRoom(robot) {
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const seen = new Set();
const goBack = () => {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
};
const dfs = (r, c, d) => {
robot.clean();
seen.add(r + "," + c);
for (let k = 0; k < 4; k++) {
const nd = (d + k) % 4;
const nr = r + dr[nd], nc = c + dc[nd];
if (!seen.has(nr + "," + nc) && robot.move()) {
dfs(nr, nc, nd);
goBack();
}
robot.turnRight();
}
};
dfs(0, 0, 0);
}Edge cases to test
- A single open cell (every move fails)
- Long corridors and dead ends, which force the robot to walk all the way back
- Loops in the open area, where a cell can be reached from two sides
- The robot's real coordinates are unknown, so you must invent your own (start = (0, 0))
Hints
Hint 1
Give the start cell the coordinates (0, 0) and keep your own record of the robot's position and facing. A set of visited coordinates tells you where you have already been.
Hint 2
This is a depth-first search where the 'recursion' is physical: after exploring a neighbour, the robot must walk back to the cell it came from and face the same direction as before.
Hint 3
Going back is: turn around (two right turns), move one step, turn around again. If you always try the four directions in clockwise order by turning right, the facing direction is easy to track.
FAQ
What is the best time complexity for Robot Room Cleaner?
Optimal (spiral backtracking DFS) runs in O(N) time and O(N) extra space. N = open cells. Each cell is entered once and each of its four sides is probed once, with a constant number of robot calls per probe.
Which pattern does Robot Room Cleaner use?
It is a recursion & backtracking problem that uses the 2d matrix backtracking pattern. Other problems with the same pattern: Word Search, Sudoku Solver.
Is there a brute force solution for Robot Room Cleaner?
Yes. Brute force (DFS that re-aims before every move) takes O(N · 4) time and O(N) space. Track the robot's absolute facing (0 = up, 1 = right, 2 = down, 3 = left).
Which edge cases should I test for Robot Room Cleaner?
A single open cell (every move fails); Long corridors and dead ends, which force the robot to walk all the way back; Loops in the open area, where a cell can be reached from two sides; The robot's real coordinates are unknown, so you must invent your own (start = (0, 0)).