I think you can solve it using a breadth-first search, maintaining no more than 2 * N^2 tuples of (boolean, int, int, int, string) where the strings are as long as the path is complicated.
The tuples are (min or max boolean, min position traveled, max position traveled, total radiation emitted, path history).
I see the algorithm going like this:
- Initialize the pool of tuples to a single entry, (min, 0, 0, 0, "")
- Find an element in the pool that has minimal radiation emitted. If the min and max correspond to the min and max of all the barrels, then the path history is the optimal solution. Otherwise delete it from the pool.
- Calculate the 2 descendants of this tuple, each of which corresponds to walking left or right to the next unprocessed barrel.
- Insert the descendants into the pool. If there is already an element in the pool with the same boolean, min, and max as a new descendent, then discard the element with the higher radiation count.
- goto 2.
Finding and removing dominated tuples will dramatically improve performance. It might be worthwhile to add a 'has bred" flag to each tuple, and leave bred tuples in the pool.
There are also some significant decisions to be made in deciding how to store the tuples, and search them for dominations and new elements to breed.