I think I would start by finding the minimum distance between each pair of mines and use that to build a graph where the weight of edge A- >B is the value of B minus the cost to get there from A. Finding the maximum cycle in a graph is NP-hard. A greedy algorithm may give a reasonably good solution, but if there are very many mines, finding the best solution becomes very expensive. Don
On Apr 29, 6:42 am, sreekanth guru <sreekanth.i...@gmail.com> wrote: > Problem: > > We have m * n grids. Each grid can have one of earth/water/mines. You can > go to top/bottom/left/right adjacent grids. You can go to adjacent grids > only when it is filled with earth/mines. you can't travers water filled > grids. To travel to adjacent grid you need to sacrifice 2 points. If you > travers mines(each mine will have some positive score) the points in that > mine will be added to your score. Now given any starting position find out > max score loop(end point should be same as start point). > > P.S. - All mine grid points can be used only once. If you traverse mine > second time you won't get any points. > > -sree -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
