Greedy Algorithm Question, Image that there is a new computer game called DownRightMOnsterous.

Problem 15. (10 points) Imagine that there is a new computer game called DowNRIGIITMONSTEROUS. 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 5x5 board will require 2 transits of the board. But this 5x5 board only requires 1 transit of the board. Describe a greedy algorithm to minimize the number of transits necessary to kil all the monsters. Prove that your algorithnm is optimal. Problem 15. (10 points) Imagine that there is a new computer game called DowNRIGIITMONSTEROUS. 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 5x5 board will require 2 transits of the board. But this 5x5 board only requires 1 transit of the board. Describe a greedy algorithm to minimize the number of transits necessary to kil all the monsters. Prove that your algorithnm is optimal