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();
}

Input: A = [1,3], B = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 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

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;

        visited.add(key);
        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