The obstacle course

Question

The obstacle course

You are currently stuck in some kind of course and you have to escape. However, if you do not choose the fastest way then the exit will close in front of you. Your challenge is to find the fastest route in an obstacle course.

Input

Your input consists of a list with lists in it, a 2D grid containing only positive integers. For example, it might look as follows:

eg. [[0,1,2],[0,3,5],[2,6,1]] which visually looks like:

0  1  2
0  3  5
2  6  1

Each number represents the time that is needed to pass the location. For example, (1,2) takes 6 seconds to pass. Your code can take for granted that no conversions of the input have to be made to make it a list that works with your language.

Computing

Your starting position will also be (1,1), which in the input above is 2. You have to include those seconds in your final answer. From your starting position your goal is to work to (xmax, ymax), which in the input above is (3,3). You have to find the fastest route to get there, so the sum of your numbers must be minimal.

Note for example understanding: the grid is from 1 and on-wards, (0,0) is not the starting position. (1,1) is bottom left and (3,3) is top right in this example.

Output

Your code must output the minimal time it takes to reach the top right corner from the bottom left corner. In the input above this is 2 + 0 + 0 + 1 + 2 = 5 seconds. Your code should output nothing else than a whole integer.

Additional specifications

• Your may not move diagonally; only left, right, down, up
• This is code-golf, shortest code in bytes wins
• The grid wont always be square, but the start will always be connected to the end
• minimum input is a 1x1 grid
• grid will only contain positive integers

To sum up the given example:

Input: [[0,1,2],[0,3,5],[2,6,1]] // any format you like
Output: 5

How:
2 + 0 + 0 + 1 + 2 = 5

Answer 1

Matlab, 207 199 bytes

Given the matrix with all the times A, the idea is using a new B matrix that has every entry set to Inf except the initial entry. Then we generate a new matrix C where we apply following formula to each pair of coordinates (i,j)

 C(i,j) = min( B(i,j), B(i-1,j)+A(i,j), B(i+1,j)+A(i,j), B(i,j-1)+A(i,j), B(i,j+1)+A(i,j) );

This means: either B(i,j) already represents the minimum time to get to (i,j) or we can get to B(i,j) quicker via one of the neighbours.

Then we replace B with C and repeat this step enough times (until nothing changes anymore), and #rows + #columns is an upper bound for this.

After that, we just need to print the top right element (or in matrix-speak: bottom right) element.

This idea is basically stolen from the Floyd-Warshall algorithm.

Note that for doing this, I need also to consider some technical details, namely that I should not access elements outside the matrix, that is why I need the zero padding and shift of coordinates.

a=input('');
[r,c]=size(a);
A=padarray(a,[1,1]);
C=A+Inf;C(2,2)=A(2,2);
for i=1:r+c
    B=C;
    for i=2:r+1;
        for j=2:c+1;
            v=[-1,1];
            C(i,j)=min([B(i,j)-A(i,j),B(i+v,j)',B(i,j+v)]+A(i,j));
        end;
    end;
end;
disp(A(r+1,c+1))

Input: We need to reverse the order of the rows due to indexing, so the example given would be

[[2,6,1];[0,3,5];[0,1,2]]

or alternatively

[2,6,1;0,3,5;0,1,2]

So for this example we get following intermediate steps that will show the progression quite nicely (I removed the padding):

 2     Inf   Inf
 Inf   Inf   Inf
 Inf   Inf   Inf

 2     8     Inf
 2     Inf   Inf
 Inf   Inf   Inf

 2     8     9
 2     5     Inf
 2     Inf   Inf

 2     8     9
 2     5    10
 2     3    Inf

 2     8     9
 2     5    10
 2     3     5

PS: I love challenges like this one=)