Minimum Cleaning-Robot Runs to Clean a Building

Reported in interviews at DRW

Problem statement

You are given a $2$D grid with $R$ rows and $C$ columns representing a building plan. Each cell is . (clean floor), * (dirty floor), or # (wall). When a cleaning robot is run somewhere, it cleans the entire floor of the room it is placed in; the robot moves up, down, left, or right, only over floor cells (. or *), and cannot pass through walls or leave the plan.

Return the minimum number of robot runs needed so that all dirty floor is cleaned.

Example:

#######
#*#.#*#
#.#.#.#
#######

The walls split the interior into three rooms. The left and right rooms each contain a * and the middle room is already clean, so the answer is $2$.

Show hint

What graph structure does a single robot run correspond to on this grid?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems