Implement all the given functions that are used to solve the below problems.

Follow the path

You are given a matrix of size m x n consisting of ones $(1)$ and zeros $(0).$ There is a single continuous path formed with ones that starts from the rightmost cell in the last row $($m$-$th row$)$ with one and ends at leftmost cell in the first row with one in it$.$ The path does not branch, and there is only one such path. Your task is to traverse along the path and print the coordinates of the path from start to end as tuples over multiple lines. The path can move vertically and horizontally.

Input

matrix $=[$

$[0,0,1,1],$

$[0,0,0,1],$

$[1,1,1,1],$

$[1,0,0,0],$

$[1,1,0,0]$

$]$

Output

$(4,1)$

$(4,0)$

$(3,0)$

$(2,0)$

$(2,1)$

$(2,2)$

$(2,3)$

$(1,3)$

$(0,3)$

$(0,2)$

def index$\_$of$\_$first$\_$occurance$($row:list,elem$)$:

$\text{'}\text{'}\text{'}$

Given a list find the index of first occurance of $1$ in it

$\text{'}\text{'}\text{'}$

$...$

def index$\_$of$\_$last$\_$occurance$($row:list,elem$)$:

$\text{'}\text{'}\text{'}$

Given a list find the index of last occurance of $1$ in it$.$

Hint: use index$\_$of$\_$first$\_$one with reversal.

$\text{'}\text{'}\text{'}$

$...$

def is$\_$valid$\_$coordinate$($x:int,y:int, M$)$:

$\text{'}\text{'}\text{'}$

Checks if the x$,$y is a valid corrdinate$($indices$)$ in the matrix M$($list of list$).$ Assume coordinates are non$-$negative

$\text{'}\text{'}\text{'}$

$...$

def valid$\_$adjacent$\_$coordinates$($x:int,y:int, M$)$:

$\text{'}\text{'}\text{'}$

Create a set of valid adjacent coordinates$($indices$)$ given x$,$y and a matrix M

$\text{'}\text{'}\text{'}$

return $\{$

$($x$1,$y$1)$

for x$1,$y$1$ in $...$ # all the possible adjacent coordinates

if is$\_$valid$\_$coordinate$($x$1,$y$1,$ M$)$

$\}$

def next$\_$coordinate$\_$with$\_$value$($curr$\_$coords, value, M$,$ prev$\_$coords$=$None$)$:

$\text{'}\text{'}\text{'}$

Find the coordinate$($indices$)$ of the next coordinate that has the $`$value$`$ in it$.$ For the starting coordinate the prev$\_$coords would be None

$\text{'}\text{'}\text{'}$

$...$

def get$\_$path$\_$coordinates$($M$)$:

$\text{'}\text{'}\text{'}$

Given the matrix m$,$ find the path formed by $1$ from the last row to the first row.

$\text{'}\text{'}\text{'}$

x$\_$start, x$\_$end $=$ len$($M$)-1,0$

y$\_$start, y$\_$end $=$ index$\_$of$\_$last$\_$occurance$($M$[-1],1),$ index$\_$of$\_$first$\_$occurance$($M$[0],1)$

$...$

def print$\_$path$($M$)$:

path $=$ get$\_$path$\_$coordinates$($M$)$

$...$

def alternate$\_$path$($M$)$:

path $=$ get$\_$path$\_$coordinates$($M$)$

$...$

def count$\_$path$($M$)$:

path $=$ get$\_$path$\_$coordinates$($M$)$

$...$

def mirror$\_$horizontally$($M$)$:

path $=$ get$\_$path$\_$coordinates$($M$)$

$...$

def mirror$\_$vertically$($M$)$:

path $=$ get$\_$path$\_$coordinates$($M$)$

$...$