Code:

# We have a directed graph.
# Use Dijkstra's graph algorithm.
a = [# / / / / /
[ 1, 100, 100, 100],#/
[ 1, 1, 100, 100],#/
[100, 1, 1, 1],#/
[100, 100, 100, 1]
]
# find the cheapest path from a[0][0] to a[3][3]
# look along the diagonals, in the direction marked.
# along diagonal just store the lowest cost and path.
def ga(a):
'''
graph algorithm. Given a rectangular matrix of weights
with restrictions that we can increment by one either the row or column
start at a[0][0] end up at a[n-1][m-1] return the lowest cost and path
Test with
shell_prompt$ python -m doctest this_file.py
>>> ga([[100, 100, 100, 100], [1, 1, 100, 100], [100, 1, 1, 1], [100, 100, 100, 1]])
(7, [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [3, 3]])
'''
n = len(a)
m = len(a[0])

Well, sorry, gotta go to a memorial for a friend's father now.
Tweet This+ 1 thisPost To Linkedin