Reach end while going through all required points

Question

Given a grid of width W and height H containing 5 type of symbols :

'S' means starting position
'E' means ending position
'C' means checkpoints
'.' means open position and player can pass through it
'#' means closed block that player cant pass through.

The aim of the player is to reach end from start in minimum distance but he need to pass all the checkpoints in the grid .

We need to find this minimum distance.

Some moves allowed to player are :

1. Player can move only by one step in horizontal or vertical(up,down,left,right) direction.
2. Diagonal movement is NOT permitted.
3. Distance is defined as number of movements to the different blocks.
4. Player can pass opened blocks,checkpoints,start and end points more than once if necessary.
5. If its not possible to arrive at goal from start then we need to tell that its not possible.

Example :

Let W=5 and H=5

# # # # #
# . C C #
# S # # #
# . . E #
# # # # #

Then here answer is 9 as path is :

(1,2)=>(1,1)=>(2,1)=>(3,1)=>(2,1)=>(1,1,)=>(1,2)=>(1,3)=>(2,3)=>(3,3)

Now W and H can go up to 100 and maximum number of checkpoints can be at max 18

One of a basic approach can be to use all pair shortest path in here.But As their can be 10000 nodes so complexity of O(N^3) by using alogrithms like Floyd-Warshall Or Dijkstra's will not serve the purpose.

So is their an better approach for this question?

Answer 1

The cost of finding paths between checkpoints is the least of your concerns. For N being the number of checkpoints, that'll grow to O(N*W*H), assuming you just do BFS out from each checkpoint (and the start and end nodes). Once you've got that easy part done, though, you still have to decide on an ordering for the checkpoints. As other commenters have pointed out, this is the travelling salesman problem, and you're not going to make it efficient -- it is unavoidably O(N!). For comparison, if we discard constant factors and use W=H=100, N=18, the cost of the shortest paths is 180000 "time units"... and the cost of finding the best ordering for the checkpoints is 6402373705728000 "time units". That, you may have noticed, is a bigger number.