This is a standard shortest path problem. Use Dijkstras. Make a graph with edge costs based on the square's nature - Harmful or Deadly. Mark edge costs for Deadly as infinity. Find the cost of the shortest path. You can also use Bellman Ford algorithm which would be simpler to implement in this case.
Note: This problem cannot be solved with a simple BFS as the node exploration order as the distance from (0,0) need not correspond to the best way to reach that square in the graph. eg. . . . . . . * x . . . * * * * s * * * * BFS will assign cost of reaching X from s as 1 (all paths considered uptil then to X will be passing through a harmful square). However, the best way to reach X is by going through the top row with cost 0. -- DK -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jXWAbvp1VcAJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
