An orienteering map is to be given in the following format. ######## #@....G# ##.##@## #..@..S# #@.....# ######## Calculate the minimum distance from the start(S) to the goal(G) with passing all the checkpoints(@). Specification ‘.’ means an openedblock that players can pass. ‘#’ means a closedblock that players cannot pass. It is allowed to move only by one step vertically or horizontally. 1 <= w <= 100, 1 <= h <= 100 The maximum number of checkpoints is 18. Return 1 if given arguments do not satisfy specifications, or players cannot arrive at the goal from the start by passing all the checkpoints. The input is to be given in the following format, from the standard input.
The first row is to describe the width and the height of the orienteering map, sectioned by a space. Output Output into the standard output, and put a return. And later I also have to print the path. asked 13 Aug '16, 15:58

You can solve this problem in 2 steps : Step 1: Create a new weighted complete graph from the input matrix , where your can add edges from source to each checkpoint and for any checkpoint to all other checkpoint and from destination to all other checkpoint. In your input example , There are three checkpoints( Let say c1 , c2 , c3 ) , one source(s) , one destination (d) . Then total edges are ( s , c1 ) ( s , c2 ) ( s , c3 ) , (c1 , c2 ) , ( c1 , c3 ) , (c2 , c3 ) ( c1 , d ) ( c2 , d ) ( c3 , d ). And if you can't reach to any checkpoint + destination from source , then you can't create the graph in that case your answer is 1. And the weight of any edge is the shortest distance between them which you can calculate by apply flood fill or any other algo like dfs/bfs on the input matrix. Step 2: Now you have complete graph , from that you have to calculate the shortest minimum path from source to destination where in between the path you have to traverse all checkpoint exactly once , means you have to find the open path from source to destination where you have to traverse all nodes exactly once. This can be solve using recursion + optimazation ( backtracking type ). In your example total possible path are : s  c1  c2  c3  d s  c1  c3  c2  d s  c2  c1  c3  d s  c2  c3  c1  d s  c3  c1  c2  d s  c3  c2  c1  d The one which will give you the minimum cost is your answer. answered 13 Aug '16, 17:25

First start a BFS from each of the checkpoints, and start and finish, in order to determine the minimum distances between any pair of checkpoints (or the start and finish). Then you've reduced the problem to the Travelling salesman problem, for which you can code a DP solution using bitmasks and solve in O(2^n * n), which is fast enough for only 18 checkpoints. I can describe the solution in more detail if you'd like. Here's a similiar problem on SPOJ: http://www.spoj.com/problems/CLEANRBT/ answered 13 Aug '16, 17:18
I understand the logic, please tell me more details about implementation part.
(14 Aug '16, 07:56)
Later I also need to find the actual path.
(14 Aug '16, 07:57)
(15 Aug '16, 18:59)
