← All solutions

This problem can be solved with dynamic programming and some geometry. First, it is intuitively clear (but a bit tricky to prove) that the edges should be visited in order, and we can guess which of the N edges we visit first.

Suppose for a while that the cleaning robot’s path does not visit any of the corners of the polygon. Then, every time the robot “bounces” against an edge of the polygon, the incoming angle of the robot’s path should equal the outgoing angle. With this observation, one can, given a starting point and a destination point and a sequence of edges to bounce against, compute the path (and in particular the length) the robot should take by reflecting the destination point around the bounce segments in reverse order. After these reflections, the path of the robot is “unwinded” to the straight line from the starting point to the new position of the destination.

However, when we are at a corner, the notion of the incoming angle breaks down and we can actually go off in any direction. This suggests a dynamic program where the state is what vertex we are currently at (either the robot’s starting point or one of the polygon vertices). Given that we are visiting the edges in order and we know which edge we visit first, the current vertex completely determines which edges are left to visit. To compute the answer from this position, we try all possibilities for the next vertex to visit, and compute the cost of bouncing all the way there as described in the previous paragraph (but note that it might not be possible from the current vertex to some subsequent vertex because it would result in the path going outside the polygon). This gives an O( N ³ ) solution.