What you need to do is create a list of all the edges and then sort them. To do this, you will need to define a class Edge:
class Edge:
def x
def y
def direction
def weight
Then, parse the h
and v
matrices and build up the edges
list. In the end, it should have 2 * N * M
elements. The direction of the edges should be either 'h'
or 'v'
, depending on the matrix that you parsed.
If you don't use the h
and v
matrices for any other purposes, you may drop them altogether, since you can compute the weights of the edges directly from the i
matrix.
Finally, for the purposes of the algorithm, you need to sort the list using the weight as a criterion:
edges.sort(key=weight)