Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

Question

If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after having collected ALL the candies. There are some cells which are blocked and hence cannot be visited. Let 10 represent empty cell, 11 represent blocked cell and 12 represent candy. So, for the given 3x3 matrix:

10 10 11
11 12 10
11 12 11

with destination: (1, 2) (0-indexed), the min. no. of moves required to go from (0,0) to (1,2) is 5. i.e (0,0)->(0,1)->(1,1)->(2,1)->(1,1)->(1,2).

How to solve this question? Since BFS, DFS, etc all avoid re-visiting visited nodes, I am unable to use them. Same goes with backtracking.

Answer 1

The fact that the total number of candies is at maximum 12 is an important constraint.

Let the candies and start and end points (total <=14 points) be key points in the grid. Now use BFS from each of the key points to find the distances between the key points, and form a new graph with only the key points. Since the number of nodes in the new graph is so small, we can use Travelling Salesman on this new graph to solve the problem.

(Note: You will need to slightly modify Travelling Salesman to work for this specific problem.)