Minimum Cleaning-Robot Runs to Clean a Building
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.