Suppose we are given annÃn grid, some of whose cells are marked; the grid is represented by an array M[1..n,1..n]of booleans, where M[i, j] =True if and only if cell (i, j) is marked. A monotone path throughthe grid starts at the top-left cell, moves only right or down at each step, and ends at the bottom-right cell. Our goal is to cover the marked cells with as few monotone paths as possible. Required:
Describe an algorithm to find a monotone path that covers the largest number ofmarked cells.