[FIXED] Cheapest path on a checkerboard from A to B. Turning and moving cost differently

Issue

We have a checkerboard with positive x and y coordinates.

0,0  1,0  2,0 ...
0,1  1,1  2,1 ...
0,2  1,2  2,2 ...
...  ...  ... ...

We have to find the cheapest path from A to B, given turning costs 100 energy and moving costs 500 each step.

I've looked into the Dijkstra Algorithm but I think that's not relevant to my problem.

What would be the easiest solution for this?

Solution

The minimum number of moves is always |X_B-X_A|+|Y_B-Y_A| and we can do it always with only one turn.

Example: move from (1,2) to (4,6):

3 moves right: 1500
1 turn:         100
4 moves down:  2000
               ----
               3600

We can't do it with less moves, only with more turns.

Answered By - Andreas Dolk