CareerCup

* -- * -- *
|     |     |
B--C -- *
|     |     |
A-- D-- *

Lets take an example. In the grid shown above
min no of steps to reach C = MIN OF {min no of steps to reach B + 1,
min no of steps to reach D + 1,
if A is a special point then min no of steps to reach A + 1
}
Use this formula and start calculating min no of steps to reach each point on the right and top of the source point, skipping those points whose X and Y coordinate exceed the X and Y coordinate of destination.

You can build a partial order on the special points. A point is bigger than another point if both its x and y coordinates are larger.
The answer is the longest path in graph build base on this order. Generally longest path is NP but this is I think a lattice which means that you can do it in poly time. Unfortunately I don't remember the algorithm for it.

You can build a partial order on the special points. A point is bigger than another point if both its x and y coordinates are larger.
The answer is the longest path in graph build base on this order. Generally longest path is NP but this is I think a lattice which means that you can do it in poly time. Unfortunately I don't remember the algorithm for it.

So, assuming the points have x and y coords and the destination is always reachable from the source (simple check that x,y of destination> x,y source), without the special points, it would be simply a case of going right till Xcurr=Xdest and then up till you hit the destination.

With special points, the trick would be to maximize the number of special points you hit. This can be done by simply starting from your current position, using an unweighted shortest path algorithm, and finding the closest special point. Then go right until Xcurr=Xspecial and then up till you hit special, jump across, and then use this as the next source, until we find that no special point is within the bounds of having it's X coord< Xdest and it Y coord<Ydest and therefore we can just go right until Xcurr=Xdest and then go up.