PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This problem is a variant of the longest-path problem, which is NP-hard. The simplest solutions simply attempted to find any path from the northwest to southeast corner, for example using a modified version of Dijkstra’s algorithm.
A better algorithm proceeds in two phases:
The first phase is to construct a graph where the vertices correspond to torches, and edges exist between 2 torches that can be reached within K steps of eachother. Then a longest-path algorithm is used to find a path that picks up as many torches as possible. For small values of K, it is difficult to visit all the torches, but for larger values of K it is quite common to be able to visit all or almost all of the torches.
The second phase is to then translate this path into a path in the original graph. The goal here is to visit as many cells as possible between each torch, and also minimize the number of cells that are visited multiple times. This can be accomplished by starting with a simple path, then augment it by adding unvisited cells to it.
TESTER’S SOLUTION
Can be found here