Solution: Number of Spaces Cleaning Robot Cleaned

Statement

You are given a 0-indexed 2D binary matrix, room, representing a room of size $m \times n$. In this matrix, $0$ represents an empty space, while $1$ represents a space occupied by an object. The top-left corner of the room is always empty in all test cases.

A cleaning robot starts at the top-left corner of the room, facing right. It moves straight until it either reaches the edge of the room or encounters an object. When this happens, it turns 90 degrees clockwise and continues moving. The robot cleans the starting space and every space it visits.

The robot continues moving indefinitely. If it visits a space again while facing the same direction, return the number of unique spaces it has cleaned.

Constraints:

• $m ==$ room.length

• $n ==$ room[r].length

• $1 \leq m, n \leq 300$

• room[r][c] is either $0$ or $1$.

• room[0][0] $==$ $0$

Solution

To solve this problem, we need to focus on three key points:

1. How does the robot start?

2. How does the robot move?

3. When does the robot stop?

The problem statement provides answers to all of these. The robot starts at position (0,0) (i.e., row = 0, column = 0), facing right. It moves forward until it encounters an edge or an obstacle; at this point, it rotates 90 degrees clockwise and continues.

The robot stops when it revisits a space while facing the same direction. But why is that the case? Let’s explore why the robot should stop when this happens.

The room is a finite grid of size $m \times n$, and the robot has four possible directions (right, down, left, up). Now, if we define the robot's state as (row, column, direction), then there can be at most $m \times n \times 4$ unique states the robot can be in. If the robot continues moving indefinitely within this finite space, it will eventually revisit a previous state. It will repeat the same movements once it returns to the same (row, column, direction). The robot is stuck in a loop, endlessly following the same cleaning pattern. Therefore, we can safely stop execution when the robot revisits a previous state, preventing it from running indefinitely.

In this solution, we'll make the robot start from the top-left corner of the room, facing right. It will keep moving in the same direction until it hits a wall or the edge of the grid. When that happens, it will rotate and continue moving. Each time the robot visits a new cell, it cleans it and marks it, along with the direction it faces, as visited, so, it doesn’t repeat movements unnecessarily. If the next cell in its current direction is free, it moves forward. Otherwise, it rotates and tries again. This process continues until the robot reaches a cell where it has already faced the current direction before, meaning it would start repeating its path. At this point, it stops and returns the total number of cells cleaned.

It's important to note that we don't use additional data structures to keep track of cleaned and visited cells in the matrix. So, how do we do it? We do it in place by manipulating bit representation slightly (through right and left shifts). We represent the robot's position and direction (row, column, and direction) as bits. This way, each cell with a 0 will have four possible representations, one for each direction.