Solution For Robot Room Cleaner
Problem Description:
Robot Room Cleaner
Given a robot cleaner in a room modeled as a grid.
Each cell in the grid can be empty or blocked.
The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.
When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.
Design an algorithm to clean the entire room using only the 4 given APIs shown below.
interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is obstacle and robot stays on the current cell.
boolean move();
// Robot will stay in the same cell after calling turnLeft/turnRight.
// Each turn will be 90 degrees.
void turnLeft();
void turnRight();
// Clean the current cell.
void clean();
}
Example:
Input:
room = [
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1]
],
row = 1,
col = 3
Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.
Notes:
The input is only given to initialize the room and the robot’s position internally. You must solve this problem “blindfolded”. In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot’s position.
The robot’s initial position will always be in an accessible cell.
The initial direction of the robot will be facing up.
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
Assume all four edges of the grid are all surrounded by the wall.
Algorithm:
To solve this problem, we follow the below-algorithm.
Create an empty set to keep track of the visited cells i.e. visited = set()
Define a dfs() function to clean the cell at the current position and mark the cell as visited
Mark the current cell as visited by adding it to the visited set, visited.add((x,y))
Clean the current cell by calling robot.clean()
Try to explore the adjacent cell of the current cell
Move the robot to the adjacent cell by calling robot.move()
Update the position of the robot to the adjacent cell, x, y = next_x, next_y
If the adjacent cell is not visited and is reachable, recursively call the function dfs with the updated position i.e. dfs(robot,x,y,d-1)
Turn the robot to the opposite direction by calling robot.turnLeft(), robot.turnLeft()
Move the robot to its previous position by calling robot.move()
Now turn the robot to a new direction by calling robot.turnLeft(). If you have started from facing up, turn left to move to the left first and then continue in a clockwise direction i.e. UP, LEFT, DOWN and RIGHT
Similarly, update the position of the robot to the next adjacent cell and repeat step 5 to 10
Have the robot turn 360 degrees unless every space has been visited, at which point it should return to the start.
Implementation:
//Definition for a binary tree node.
//class Robot {
// public:
// bool move();
// void turnLeft();
// void turnRight();
// void clean();
//};
class Solution {
public:
set
void dfs(Robot& robot, int x, int y, int d) {
robot.clean();
visited.insert({x,y});
for(int i=0;i<4;++i) {
int next_x=x,next_y=y;
if(i==0){//go to up
robot.turnLeft();
}else if(i==1){//go to right
robot.turnLeft();
robot.turnLeft();
}else if(i==2){//go to down
robot.turnRight();
}else{//go to left
//robot may have already started in this position, so don’t turn left twice
}
if(robot.move()) {
if(!visited.count({next_x-1,next_y}) && i==0){
dfs(robot,next_x-1,next_y,d-1);
}else if(!visited.count({next_x,next_y+1}) && i==1){
dfs(robot,next_x,next_y+1,d-1);
}else if(!visited.count({next_x+1,next_y}) && i==2){
dfs(robot,next_x+1,next_y,d-1);
}else if(!visited.count({next_x,next_y-1}) & i==3){
dfs(robot,next_x,next_y-1,d-1);
}
robot.turnLeft();
robot.turnLeft();
robot.move();
if(i==0){
robot.turnRight();
}else if(i==1){
robot.turnRight();
robot.turnRight();
}else if(i==2){
robot.turnLeft();
}else{
//robot may have already started in this position, so don’t turn right twice
}
}else{
if(i==0){
robot.turnRight();
}else if(i==1){
robot.turnRight();
robot.turnRight();
}else if(i==2){
robot.turnLeft();
}else{
robot.turnLeft();//turn left to face up direction
}
}
}
void cleanRoom(Robot& robot) {
dfs(robot,0,0,4*10^4);
}
};
Time Complexity:
The time complexity of the solution is O(4^n) where n is the number of cells in the room. Since we visit each cell exactly once, and the worst-case complexity can occur when the room is a grid with a size of n* n i.e. n^2 cells.
Space Complexity:
The space complexity of the solution is O(n^2) since we use a set to keep track of the visited cells. In the worst-case scenario, we might have to visit all n^2 cells.
Step by Step Implementation For Robot Room Cleaner
/*
This is a Java solution for the leetcode problem "robot-room-cleaner".
The problem is as follows:
Given a robot cleaner in a room modeled as a grid.
Each cell in the grid can be empty or blocked.
The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.
When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.
Design an algorithm to clean the entire room using only the 4 given APIs shown below.
interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is obstacle and robot stays on the current cell.
boolean move();
// Robot will stay on the same cell after calling turnLeft/turnRight.
// Each turn will be 90 degrees.
void turnLeft();
void turnRight();
// Clean the current cell.
void clean();
}
Example:
Input:
room = [
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1]
],
row = 1,
col = 3
Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at row 1, col 3.
From the top left corner, its position is one row below and three columns right.
Notes:
- The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.
- The robot's initial position will always be in an accessible cell.
- The initial direction of the robot will be facing up.
- All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
- Assume all four edges of the grid are all surrounded by wall.
*/
/**
* // 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.
* // Each turn will be 90 degrees.
* public void turnLeft();
* public void turnRight();
*
* // Clean the current cell.
* public void clean();
* }
*/
class Solution {
// going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
Set> visited = new HashSet<>();
Robot robot;
public void goBack() {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
public void cleanRoom(Robot robot) {
this.robot = robot;
backtrack(robot, 0, 0, 0);
}
public void backtrack(Robot robot, int row, int col, int d) {
visited.add(new Pair(row, col));
robot.clean();
// try each possible move starting from the current cell
for (int i = 0; i < 4; i++) {
int newD = (d + i) % 4;
int newRow = row + dirs[newD][0];
int newCol = col + dirs[newD][1];
// if the new cell is not visited and is open
if (!visited.contains(new Pair(newRow, newCol)) && robot.move()) {
// move the robot into the new cell and clean it
backtrack(robot, newRow, newCol, newD);
// go back to the previous cell
goBack();
}
// turn the robot to face the next possible cell
robot.turnRight();
}
}
} def cleanRoom(self):
"""
:type robot: Robot
:rtype: None
"""
# use a set to track visited cells
visited = set()
# define directions
dirs = [(0,1), (1,0), (0,-1), (-1,0)]
# define a backtracking function
def backtrack(cell=(0,0), d=0):
# mark the current cell as visited
visited.add(cell)
# clean the current cell
robot.clean()
# for each next cell
for i in range(4):
# compute next cell
next_d = (d + i) % 4
next_cell = (cell[0] + dirs[next_d][0], cell[1] + dirs[next_d][1])
# if next cell is not visited and is reachable
if next_cell not in visited and robot.move():
# backtrack from the next cell
backtrack(next_cell, next_d)
# go back to the current cell
robot.turnLeft()
robot.turnLeft()
robot.move()
robot.turnLeft()
robot.turnLeft()
# start backtracking from the initial cell (0,0)
backtrack()// This is a robot cleaning problem from leetcode. // The robot is given a room with m x n dimensions. // The robot starts at the top left corner of the room (0, 0) // and can move to the four directions - up, down, left, right. // The robot can only clean the floor tiles in the same room // and once it cleans a tile, it cannot clean it again. // // Your task is to write a Javascript function that // will take in the dimensions of the room // and the starting position of the robot // and will return the minimum number of steps // required for the robot to clean the entire room. // // For example, given the following inputs: // // m = 2 // n = 3 // startingPosition = [1, 1] // // The minimum number of steps required to clean the room // is 5. The robot needs to make the following moves: // // Move right // Move down // Move left // Move down // Move right // // The robot cannot make any more moves after making the // last move because it is already at the bottom right // corner of the room (2, 3). // // Here is the function signature: // // function minimumSteps(m, n, startingPosition) { // // your code here // }/**
* // 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.
* // Each turn will be 90 degrees.
* void turnLeft();
* void turnRight();
*
* // Clean the current cell.
* void clean();
* };
*/
class Solution {
public:
void cleanRoom(Robot& robot) {
unordered_set visited;
dfs(robot, visited, 0, 0, 0);
}
void dfs(Robot& robot, unordered_set& visited, int i, int j, int cur_dir) {
string key = to_string(i) + "-" + to_string(j);
if (visited.count(key)) {
return;
}
visited.insert(key);
robot.clean();
for (int n = 0; n < 4; n++) {
if (robot.move()) {
int x = i, y = j;
switch(cur_dir) {
case 0:
x = i - 1;
break;
case 1:
y = j + 1;
break;
case 2:
x = i + 1;
break;
case 3:
y = j - 1;
break;
}
dfs(robot, visited, x, y, cur_dir);
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
robot.turnRight();
cur_dir = (cur_dir + 1) % 4;
}
}
}; /**
* // 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.
* // Each turn will be 90 degrees.
* public void turnLeft();
* public void turnRight();
*
* // Clean the current cell.
* public void clean();
* }
*/
public class Solution {
public void CleanRoom(Robot robot) {
// use a set to keep track of visited cells
HashSet visited = new HashSet();
// starting cell
int currX = 0;
int currY = 0;
// starting direction
int currDirection = 0;
// add starting cell to visited set
visited.add(currX + "," + currY);
// call dfs helper function
dfs(robot, visited, currX, currY, currDirection);
}
public void dfs(Robot robot, HashSet visited, int currX, int currY, int currDirection) {
// base case - all cells have been visited
if(visited.size() == 25) {
return;
}
// clean current cell
robot.clean();
// try to move in all 4 directions
for(int i = 0; i < 4; i++) {
// calculate next cell coordinates
int nextX = currX;
int nextY = currY;
if(currDirection == 0) {
nextY++;
}
else if(currDirection == 1) {
nextX++;
}
else if(currDirection == 2) {
nextY--;
}
else if(currDirection == 3) {
nextX--;
}
// check if next cell is valid and not visited
if(!visited.contains(nextX + "," + nextY) && robot.move()) {
// mark next cell as visited
visited.add(nextX + "," + nextY);
// recursive call dfs helper function
dfs(robot, visited, nextX, nextY, currDirection);
// once all cells in current direction have been visited, backtrack
robot.turnLeft();
robot.turnLeft();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
// turn robot to next direction
robot.turnRight();
currDirection = (currDirection + 1) % 4;
}
}
} 