Marathon Match 119
Topcoder MM 119 - HardestMaze is now live!
Problem Setter: dimkadimon
Problem Testers: JacoCronje and kphmd
Problem Overview:
You want to create a maze to test the navigating ability of robot vacuum cleaners. The maze is to be designed on an **N**x**N** grid floor, whose cells are either empty ('.') or contain a wall ('#'). There are **R** robots and each robot must visit **T** target locations. In particular, each robot **r** begins in location **Starts[r]** and must visit every location given in **Targets[r]**. The robots do not need to return to their starting location at the end of their journey. The robots can only move through adjacent (horizontally or vertically) empty cells. The robots can see the entire maze and will choose the *shortest* path that visits all their target locations. Some paths of the robot may overlap and these are all counted towards the total distance. Your goal is to make the maze as hard as possible, ie., to maximize the total distance travelled by all the robots.
For example, here is a solution for seed=1. There are 2 robots (crosses) and each must visit 2 target locations (circles). The shortest path for each robot is shown with a different colour. Note that some paths may overlap — this is ok as robots do not interfere with each other.
Best of luck!
- the Topcoder Team
