Robot Room Cleaner Leetcode Solution

Difficulty Level Hard
Frequently asked in Amazon ByteDance Facebook Google Microsoft
Backtracking interactive tiktokViews 5706

Problem Statement

The Robot Room Cleaner LeetCode Solution – “Robot Room Cleaner” states that given the robot in a m x n a binary grid where 0 represents a wall and 1 represents an empty slot.

The initial position of the robot is guaranteed to be empty and the robot moves inside the grid using the given API Robot. The Robot has to clean every empty cell in the room.

API Robot has the following functions:

  • boolean move(): returns true if the next cell is reachable without any obstacle, otherwise false.
  • void turnLeft(): turns left
  • void turnRight(): turns right
  • function void clean(): cleans the current room.

Example:

Robot Room Cleaner Leetcode Solution

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
Output: Robot cleaned all rooms.

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 position row = 1, col = 3.
  • From the top-left corner, its position is one row below and three columns right.
Input:  room = [[1]], row = 0, col = 0
Output: Robot cleaned all rooms.

Approach

Idea:

  1. The main idea to solve this problem is to use Recursionwith Backtracking.
  2. Start with the API of the robot and the current reference location (0,0).
  3. Also, Maintain a HashSet that stores the visited cells with respect to the reference location.
  4. Now, for each position, explore all four adjacent directions and check whether the robot is able to move in that direction or not?
  5. Also, check that the new coordinate must be unvisited.
  6. Explore the new coordinate if the above points are true.
  7. Also, to return back to the same cell with the same orientation of the robot, we will turn the robot two times right, then move to the previous cell, then again two times right to store back the previous orientation.
  8. Above procedure, cleans all the rooms since robot visits every room.

Code

Robot Room Cleaner Leetcode C++ Solution:

class Solution {
public:
    set<array<int,3>> vis;
    void dfs(int x,int y,int dir,Robot& robot){
        robot.clean();
        for(int d=0;d<4;d++){
            int new_dir = (dir+d)%4;
            if(new_dir==0 and !vis.count({x-1,y,new_dir}) and robot.move()){
                vis.insert({x-1,y,new_dir});
                dfs(x-1,y,new_dir,robot);
            }
            if(new_dir==1 and !vis.count({x,y+1,new_dir}) and robot.move()){
                vis.insert({x,y+1,new_dir});
                dfs(x,y+1,new_dir,robot);
            }
            if(new_dir==2 and !vis.count({x+1,y,new_dir}) and robot.move()){
                vis.insert({x+1,y,new_dir});
                dfs(x+1,y,new_dir,robot);
            }
            if(new_dir==3 and !vis.count({x,y-1,new_dir}) and robot.move()){
                vis.insert({x,y-1,new_dir});
                dfs(x,y-1,new_dir,robot);
            }
            robot.turnRight();
        }
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }
    void cleanRoom(Robot& robot) {
        dfs(0,0,0,robot);
    }
};

Robot Room Cleaner Leetcode Java Solution:

class Solution {
    public void dfs(int x,int y,int dir,Robot robot,Set<String> vis){
        robot.clean();
        for(int d=0;d<4;d++){
            int new_dir = (dir+d)%4;
            if(new_dir==0 && !vis.contains((x-1)+" "+y) && robot.move()){
                vis.add((x-1)+" "+y);
                dfs(x-1,y,new_dir,robot,vis);
            }
            if(new_dir==1 && !vis.contains(x+" "+(y+1)) && robot.move()){
                vis.add(x+" "+(y+1));
                dfs(x,y+1,new_dir,robot,vis);
            }
            if(new_dir==2 && !vis.contains((x+1)+" "+y) && robot.move()){
                vis.add((x+1)+" "+y);
                dfs(x+1,y,new_dir,robot,vis);
            }
            if(new_dir==3 && !vis.contains(x+" "+(y-1)) && robot.move()){
                vis.add(x+" "+(y-1));
                dfs(x,y-1,new_dir,robot,vis);
            }
            robot.turnRight();
        }
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }
    public void cleanRoom(Robot robot) {
        dfs(0,0,0,robot,new HashSet<>());
    }
}

Complexity Analysis for Robot Room Cleaner Leetcode Solution

Time Complexity

The time complexity of the above code is O(row*col) since we traverse the entire matrix in the worst case.

Space Complexity

The space complexity of the above code is O(row*col). In the Worst Case, the HashSet store all cells hence, O(row*col).

Reference: https://en.wikipedia.org/wiki/Hash_function

Translate »