How to solve such questions based on maze

general
, ,
1

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 opened-block that players can pass.
‘#’ means a closed-block 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.

  W H
  Row1
  Row2   
   ...
  RowH

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.

@likecs, @uwi

2

could you plzz provide the link for this question so that i can understand complete question

3

@shobhit99924

4

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:

5

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.

6

@linkret

I understand the logic, please tell me more details about implementation part.

7

@linkret

Later I also need to find the actual path.

8

@vipsharmavip

Can you help me to code this, I couldn’t.

It would be great help if you could.

9

@linkret

Can you help me to code this, I couldn’t.

It would be great help if you could.

10

@shobhit99924

Can you help me to code this, I couldn’t.

It would be great help if you could.