Robot Room Cleaner

hard backtracking dfs interactive

Problem

A robot in an unknown grid can move(), turnLeft()/turnRight(), and clean(). Cells are 0 (obstacle) or 1 (cell). Clean every reachable cell.

Inputgrid = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,0,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], start = (1,3)

Outputall reachable cells cleaned

DFS records visited (x,y) in a set; backtrack uses two 180° rotations so the robot ends where it started.

grid (rows ; , 1=cell, 0=wall)

def clean_room(robot):
    DIRS = [(-1,0),(0,1),(1,0),(0,-1)]
    visited = set()
    def dfs(x, y, d):
        robot.clean(); visited.add((x, y))
        for k in range(4):
            nd = (d + k) % 4
            nx, ny = x + DIRS[nd][0], y + DIRS[nd][1]
            if (nx, ny) not in visited and robot.move():
                dfs(nx, ny, nd)
                robot.turnRight(); robot.turnRight(); robot.move()
                robot.turnRight(); robot.turnRight()
            robot.turnRight()
    dfs(0, 0, 0)

function cleanRoom(robot) {
  const DIRS = [[-1,0],[0,1],[1,0],[0,-1]];
  const seen = new Set();
  function dfs(x, y, d) {
    robot.clean(); seen.add(x + "," + y);
    for (let k = 0; k < 4; k++) {
      const nd = (d + k) % 4;
      const nx = x + DIRS[nd][0], ny = y + DIRS[nd][1];
      if (!seen.has(nx + "," + ny) && robot.move()) {
        dfs(nx, ny, nd);
        robot.turnRight(); robot.turnRight(); robot.move();
        robot.turnRight(); robot.turnRight();
      }
      robot.turnRight();
    }
  }
  dfs(0, 0, 0);
}

class Solution {
    int[][] DIRS = {{-1,0},{0,1},{1,0},{0,-1}};
    Set seen = new HashSet<>();
    public void cleanRoom(Robot r) { dfs(r, 0, 0, 0); }
    void dfs(Robot r, int x, int y, int d) {
        r.clean(); seen.add(x + "," + y);
        for (int k = 0; k < 4; k++) {
            int nd = (d + k) % 4, nx = x + DIRS[nd][0], ny = y + DIRS[nd][1];
            if (!seen.contains(nx + "," + ny) && r.move()) {
                dfs(r, nx, ny, nd);
                r.turnRight(); r.turnRight(); r.move();
                r.turnRight(); r.turnRight();
            }
            r.turnRight();
        }
    }
}

void dfs(Robot& r, int x, int y, int d, set>& seen, vector>& DIRS) {
    r.clean(); seen.insert({x, y});
    for (int k = 0; k < 4; k++) {
        int nd = (d + k) % 4, nx = x + DIRS[nd].first, ny = y + DIRS[nd].second;
        if (!seen.count({nx, ny}) && r.move()) {
            dfs(r, nx, ny, nd, seen, DIRS);
            r.turnRight(); r.turnRight(); r.move();
            r.turnRight(); r.turnRight();
        }
        r.turnRight();
    }
}
void cleanRoom(Robot& r) {
    vector> DIRS = {{-1,0},{0,1},{1,0},{0,-1}};
    set> seen;
    dfs(r, 0, 0, 0, seen, DIRS);
}

Explanation

The robot cannot see the room — it can only move, turn, and clean. So we explore with DFS while tracking its position ourselves using made-up coordinates, starting from (0, 0).

We keep a visited set of cleaned cells. At each cell we clean it, then try all four directions. The clever part is the DIRS array combined with (d + k) % 4: it lets us try directions relative to whichever way the robot currently faces, so our coordinate math always matches the robot's real heading.

If the next cell is unvisited and robot.move() succeeds (no wall), we recurse into it. When that recursion finishes, we must put the robot back exactly where it was — that is the backtracking step: turnRight twice (a 180° turn), move one step back, then turnRight twice again to restore the original facing.

After handling a direction (whether we moved or hit a wall), one more turnRight rotates the robot to line up with the next direction in our loop.

Example: starting in an open area, the robot cleans its cell, drives north as far as it can, carefully reverses back down the same corridor, then peels off to clean east, west, and south — eventually covering every reachable cell and returning to start.

Time: O(N − M) Space: O(N − M)