Walking around Marks and Spencers, I noticed that they had air conditioning units placed randomly around the shop. Wanting to keep cool, I wondered what was the easiest way to move around the whole shop without being away from an air conditioning unit for too long.
Given a map, you must find a way to travel around the whole map keeping the distance from an air conditioning unit as short as possible (even if the AC unit is on the other side of a wall).
The map may be supplied in any way you like and uses the following symbols:
+ is a corner of a wall | is a east/west facing wall - is a north/south facing wall X is an air conditioning unit S is the start and end point
An example map would be:
+------S---+ | X | | ---+-+ X | | |X| | | ---+ +---+ | X | +----------+
+---+--+ | X | | | | +-----+------+ | | X | X | | ---+ | S | | | X | | | | +-+-------+--+ | X | +------+
Travelling around the whole map means passing through every empty space and air conditioner. You cannot travel through a wall and may only travel orthogonally. A map may not always be rectangular.
Keeping the distance as short as possible from an AC unit is the sum over all time steps.
Passing through means entering and leaving.
You may output the path in any way you like. Examples include:
- Outputting the map with the path included
- Outputting the path as a succession of compass points (e.g.