Problem $3.(10$ points$)$ Imagine that there is a new computer game called DownRightMonsterous. The playing

area is shaped like an NxN checkerboard and some of the squares contain monsters $($that you need to kill$).$ You

begin in the top left corner and take steps either down or to the right until you reach the bottom right corner. If

you step onto a square with a monster, you kill the monster. If you reach the bottom right square and all monsters

have been killed then you win. If you reach the bottom right square and there are monsters still alive you are moved

back to the top left corner and need to kill the remaining monsters. Your goal is to kill all of the monsters in the

minimum number of transits of the board.

For example, this $5$x$5$ board will require $2$ transits of the board.

M

M

But this $5$x$5$ board only requires $1$ transit of the board.

M

M

M M M

M

Describe a greedy algorithm to minimize the number of transits necessary to kill all the monsters. Prove that your

algorithm is optimal.