JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes Complex graph problem!!
 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.
 Forums TopCoder Cookbook Algorithm Competitions - New Recipes Complex graph problem!! Previous Thread  |  Next Thread