My first try, I wrote an algorithm that would just find random ways through the matrix and then give me the solution that comes out. I think there was something wrong in that initial one because it gave me numbers that ended up being way too small.
The final code, I kept a variable that represented the places in the matrix that should be tested the next go around. For each of those spots, it checks to see if the path through it was less than the other paths already compiled. Then it would add to the variable the points above, below, and to the right of it; those points that should be tested on the next go around.
If the tested point did not yield a smaller value, it’s point above, below, or to the right was not added to the list. This meant that when the list was empty, the final value was found.
small = 10**8
empty = nothing()
visite = []
for start in range(80):
visite.append([start, 0])
empty[start][0] = matrix[start][0]
while len(visite) != 0:
v = visite[0]
if v[0] != 79:
visite.append([v[0]+1, v[1]])
if empty[v[0]][v[1]] + matrix[v[0]+1][v[1]] < empty[v[0]+1][v[1]]:
empty[v[0]+1][v[1]] = empty[v[0]][v[1]] + matrix[v[0]+1][v[1]]
else:
visite.pop()
if v[0] != 0:
visite.append([v[0]-1, v[1]])
if empty[v[0]][v[1]] + matrix[v[0]-1][v[1]] < empty[v[0]-1][v[1]]:
empty[v[0]-1][v[1]] = empty[v[0]][v[1]] + matrix[v[0]-1][v[1]]
else:
visite.pop()
if v[1] != 79:
visite.append([v[0], v[1]+1])
if empty[v[0]][v[1]] + matrix[v[0]][v[1]+1] < empty[v[0]][v[1]+1]:
empty[v[0]][v[1]+1] = empty[v[0]][v[1]] + matrix[v[0]][v[1]+1]
else:
visite.pop()
del visite[0]
for e in empty:
if e[-1] < small:
small = e[-1]
print small