A robot must clean all corridors in a building. Assume that the robot can clean a corridor by simply traversing it and the robot always chooses to clean a corridor next to its current room that was least recently cleaned. We want to know how long (in the number of corridors traversed) will it take for the robot to clean all corridors at least once? We show that an exponential number of steps is sufficient and necessary in the worst case. This answers a conjecture by Messinger and Nowakowski in the negative. We show other ways to choose the next corridor which lead to a polynomial worst-case cleaning time. We also look at other variants of this problem such as when there is more than one robot.