| Bytes | Lang | Time | Link |
|---|---|---|---|
| 361 | Python3 | 240523T224428Z | Ajax1234 |
| 199 | Matlab | 151026T210014Z | flawr |
Python3, 361 bytes
Optimized to work on larger obstacle courses. See TIO link for more test cases.
def f(b):
q,s=[(0,0,b[0][0],[(0,0)])],[sum(b[0])+sum(i[-1]for i in b[1:]),sum(b[-1])+sum(i[0]for i in b[:-1])]
for x,y,t,p in q:
if(x,y)==(J:=len(b)-1,K:=len(b[0])-1):s+=[t];continue
for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
n,m=x+X,y+Y
if 0<=n<=J and 0<=m<=K and(n,m)not in p and(s==[]or t+b[n][m]<min(s)):q+=[(n,m,t+b[n][m],p+[(n,m)])]
return min(s)
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=)