# Robot Room Cleaner

This page explains Java solution to problem `Robot Room Cleaner` using `Depth First Search` algorithm.

## Problem Statement

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.

``````
/**
* 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.
**/
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 1:

Input: A = [1,3], B = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2

Example 2:

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]
],
Output: Your Program should visit each cell once

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class RobotRoomCleaner {
/**
* 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.
**/
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();
}

public void cleanRoom(Robot robot) {
HashSet<String> visited = new HashSet<>();
helper(robot, 0, 0, 0, visited);
}

private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

private void helper(Robot robot, int x, int y, int direction, HashSet<String> visited) {
String key = x + " "+ y;
if(visited.contains(key)) return;

robot.clean();

for(int i = 0; i < dirs.length; i++) {
if(robot.move()) {
int xNew = x + dirs[direction][0];
int yNew = y + dirs[direction][1];

helper(robot, xNew, yNew, direction, visited);

robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
robot.turnRight();
direction = (direction + 1) % 4;
}
}
}

``````

## Time Complexity

O(N - M) Where
N is total number of empty cell in an input grid
M is total number of obstacles in an input grid

## Space Complexity

O(N - M) Where
N is total number of empty cell in an input grid
M is total number of obstacles in an input grid