Solution by nikaj

Move the robots to some initial positions and use the same zigzag (snake) pattern for all of them to cover the whole grid.

If we fix the zigzag pattern (RRR..D LLL..D ..), for each starting position (trying all 8 direction rotations) we can calculate its coverage. By performing set cover (using simple SA) we will try to cover the whole board. If successful, we do the additional step: keep the full coverage but minimize the total distance robots would have to travel to the initial positions (using precomputed distances).

After that, in the second stage we use a greedy method that can create buttons (other than the 4 buttons used for the zigzag). We press the best existing button if the sum of distances decreases; otherwise, create a new button. If this stage is a success, we have a solution.

Depending on pattern sizes (which would correspond to rectangle dimensions if there were no walls) and randomness, our attempt may fail (when rectangles are small or SA finds bad coverage). To mitigate this, we restart the process with random length and width for the remaining time (having a lightweight SA allows a few dozen attempts).

Bugs fixed after contest (fixed submission gets >386K):

• Only need 3 directions for the zigzag; one button was semi-wasted.
• Pruning for pattern size was in the wrong place.