JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Complex graph problem!! | Reply
Hi to all!
I am stuck on a good problem. I am given a 2 D matrix containing
'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 :

Player can move only by one step in horizontal or vertical(up,down,left,right) direction.
Diagonal movement is NOT permitted.
Distance is defined as number of movements to the different blocks.
Player can pass opened blocks,checkpoints,start and end points more than once if necessary.
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.

What would be the most optimal approach for this ?

My approach : Finding all pair shortest paths.
RSS