Robot Room Cleaner - Leetcode Solution

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<pair<int, int>> visited; 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.

1