Interview Question
Country: United States
if there is no @ in the matrix then find the min distance between S and G
for example in the above path is 4
the question is
########
#@....G#
##.##@##
#..@..S#
#@.....#
########
here
* 'S' means the orienteering start.
* 'G' means the orienteering goal.
* '@' means an orienteering checkpoint.
* '.' 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 (up, down, left, or right) to the
next block.
Other types of movements, such as moving diagonally (left up, right up, left down and right down)
and skipping one or more blocks, are NOT permitted.
* You MUST NOT get out of the map.
* Distance is to be defined as the number of movements to the different blocks.
* You CAN pass opened-blocks, checkpoints, the start, and the goal more than once if necessary.
* You can assume that parameters satisfy following conditions.
* 1 <= width <= 100
* 1 <= height <= 100
* The maximum number of checkpoints is 18.
The aim of this game is to arrive at the goal (G) from the start (S) with the shortest distance.
However, the players have to pass all the checkpoints (@) on the map.
if the input is given in this format .....i arrived at a solution without "@" constraints
by doing BFS and got the solution b/w start and goal which is simple maze problem ....but iam stuck ...i mean i am not understanding how to tackle @ symbols...it wouls be great if someone could come up with a solution or a hint
this is a question of an ongoing placement process by WAP,so it's requested not to answer it till 26th aug.Students querying about this who registered in WAP current placement process will be rejected.
- mukaosu chang August 21, 2014