Problem Explanation and Solution Approach

The problem presents a scenario where we have a robot inside a room that's modeled as a grid where each cell is either blocked(0) or empty(1). The robot has been programmed to perform 4 tasks: move, turn left, turn right and clean the cell it is currently in.

Our task is to design an algorithm that allows the robot to clean the entire room using the 4 tasks mentioned above.

The challenge in this problem is that we do not know the layout of the room(grid) and the initial position of the robot. We can only control the robot by calling the 4 tasks available. This type of problem can be solved using Depth-first search(DFS) strategy because of the way DFS explore each branch of the problem fully before backtracking.

Walkthrough example

Let's walkthrough an example:

Given room layout :-

1
2
3room = [
4  [1,1,1,1,1,0,1,1],
5  [1,1,1,1,1,0,1,1],
6  [1,0,1,1,1,1,1,1],
7  [0,0,0,1,0,0,0,0],
8  [1,1,1,1,1,1,1,1]
9]

Where 0 represents blocked cells and 1 represents the empty cells where the robot can clean. Suppose robot Initial position is row=1, col=3,i.e., it starts at the fourth cell of the second row.

Digitally, it's like this:

1
2
3[1,1,1,R,1,0,1,1],
4[1,1,1,1,1,0,1,1],
5[1,0,1,1,1,1,1,1],
6[0,0,0,1,0,0,0,0],
7[1,1,1,1,1,1,1,1]

Where R represents the robot. Now the robot, following DFS strategy, will move forward and continue to clean the room until it gets blocked, then it will turn 90 degrees to its right and start moving in that direction and the process will continue. During this process, it will maintain a record of all the cells it has visited using the 'seen' variable, so that it doesn't get stuck in a loop.

Solution

Java

1
2java
3// This class represents the robot's control interface.
4interface Robot {
5    // Returns true if the cell in front is open, false if it is blocked.
6    boolean move();
7
8    // Robot will stay in the same cell after making a turn. Each turn is 90 degrees.
9    void turnLeft();
10    void turnRight();
11
12    // This cleans the current cell.
13    void clean();
14}
15
16class Solution {
17    // the directions: up, right, down, left (clock-wise)
18    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
19   
20    public void cleanRoom(Robot robot) {
21        // Run dfs from the robot's start position (0, 0) and initially it is facing up with index 0 in `dirs`
22        dfs(robot, new HashSet<>(), 0, 0, 0);
23    }
24   
25    private void dfs(Robot robot, Set<String> visited, int x, int y, int dir) {
26        String path = x + "-" + y;
27        if (visited.contains(path)) return;
28        
29        visited.add(path);
30        
31        robot.clean();
32        
33        // explore 4 directions: up, right, down, and left (in clockwise order)
34        for (int k = 0; k < 4; k++) {
35            // the upcoming direction
36            int newDir = (dir + k) % 4;
37            int newX = x + dirs[newDir][0];
38            int newY = y + dirs[newDir][1];
39            path = newX + "-" + newY;
40           
41            if (!visited.contains(path) && robot.move()) {
42                dfs(robot, visited, newX, newY, newDir);
43                // backtrack 
44                goBack(robot);
45            }
46            // turn to the next direction (clockwise)
47            robot.turnRight();
48        }
49    }
50   
51    private void goBack(Robot robot) {
52        robot.turnRight();
53        robot.turnRight();
54        robot.move();
55        // turn back to the original direction
56        robot.turnRight();
57        robot.turnRight();
58    }
59}

For Python, JavaScript, C++, C# solutions, please refer to the companies associated classes.## Python

1
2python
3class Solution:
4    def cleanRoom(self, robot):
5        def go_back():
6            robot.turnRight()
7            robot.turnRight()
8            robot.move()
9            robot.turnRight()
10            robot.turnRight()
11        
12        def dfs(cell = (0, 0), d = 0):
13            visited.add(cell)
14            robot.clean()
15            # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
16            for i in range(4):
17                new_d = (d + i) % 4
18                new_cell = (cell[0] + directions[new_d][0], \
19                            cell[1] + directions[new_d][1])
20                
21                if not new_cell in visited and robot.move():
22                    dfs(new_cell, new_d)
23                    go_back()
24                # turn the robot following chosen direction : clockwise
25                robot.turnRight()
26    
27        # going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
28        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
29        visited = set()
30        dfs()

JavaScript

1
2javascript
3class Solution {
4    constructor(robot) {
5        this.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
6        this.robot = robot;
7        this.dfs = this.dfs.bind(this);
8        this.goBack = this.goBack.bind(this);
9    }
10    cleanRoom() {
11        this.dfs(0, 0, 0, new Set());
12    }
13    dfs(x, y, dir, visited) {
14        const coords = `${x}-${y}`;
15        if (visited.has(coords)) return;
16        visited.add(coords);
17        this.robot.clean();
18        for (let i = 0; i < 4; i++) {
19            const newDir = (dir + i) % 4;
20            const newX = x + this.directions[newDir][0];
21            const newY = y + this.directions[newDir][1];
22            if (!visited.has(`${newX}-${newY}`) && this.robot.move()) {
23                this.dfs(newX, newY, newDir, visited);
24                this.goBack();
25            }
26            this.robot.turnRight();
27        }
28    }
29    goBack() {
30        this.robot.turnRight();
31        this.robot.turnRight();
32        this.robot.move();
33        this.robot.turnRight();
34        this.robot.turnRight();
35    }
36}

The above codes work by recursively checking four directions in a clockwise order, initiating the robot to move and clean when possible. After cleaning, the robot backtracks via the 'goBack' function which moves the robot back to its previous step and keeps its original direction. The robot keeps track of the visited coordinates to avoid revisiting them.