A path matrix is a matrix of 0s and 1s that holds a single continuous path
of 1s. The path starts at the rightmost 1 of the last row and ends at the
leftmost 1 of the first row. It does not branch, and it moves only horizontally
and vertically.
matrix = [
[0, 0, 1, 1],
[0, 0, 0, 1],
[1, 1, 1, 1],
[1, 0, 0, 0],
[1, 1, 0, 0]
]
Write count_path(M) that finds the path and then numbers its cells in order of
travel: the start cell becomes 1, the next cell 2, and so on up to the length
of the path at the end cell. Cells that are not on the path keep their value.
Modify M in place and return it.
Example
For M = [[1, 0, 0], [1, 0, 0], [1, 1, 1]] the path is
[(2, 2), (2, 1), (2, 0), (1, 0), (0, 0)], so the result is
[[5, 0, 0], [4, 0, 0], [3, 2, 1]].
Implement this function:
def count_path(M):
Write the function only — the arguments are read for you and the return value is printed automatically.
Arguments arrive as one Python literal per line, in this order: M.
Input
[[0, 0, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0]]
Output
[[0, 0, 10, 9], [0, 0, 0, 8], [4, 5, 6, 7], [3, 0, 0, 0], [2, 1, 0, 0]]