In this project, you will extend the dynamic programming algorithm that we discussed in class for the Coin Collection problem in a two-dimensional grid and implement the same The conditions for the robot movement are as follows: at any timc, the robot can move one cell down or one cell to the right One cell to the right One cell down Each of you are assigned a grid of dimensions n (roms) x m (columns) as specified in the next page.You are required to randomly distribute P number of coins (where Pcn"m) across the cells of the grid (at most one coin per cell). The value for a coin assigned to a cell is randomly chosen from the range 1 V The P and V values are also assigned specifically for each student. Your tasks are as follows: (1) Implement the dynamic programming algorithm to cakculate the optimum (maximam) value of the coins that a robot could collect as it traverses from cell (0,0) to any cell in the grid such that at any time, a robot can have one of the two movements mentioned above. (2) Extend the dynamic programming algorithm to also keep track of the path traced by the robot to reach any target cell in the grid starting from cell (0,)Clearly explain the logic of your algorithm to keep track of the path traced (3) As output, your code should print the following G) The optimum valuc of the coins that a robot could colloct to reach any target cell in the grid starting from cell (0, 0), as shown in the table sample output (see next page. Gin) The sequence of cells that the robot should visit to collect the optimum valee of the coins starting from cell (0, 0) to cell (B-Lm-1). (ii) The total number of horizontal movements (one cell to the right) and the individual horizontal movements as well as the total mamber of vertical movements (one cell down) and the individual vertical movements that the robot needs to make to collect the optimum value of the coins starting from cell (0, 0) to cell (n-I, m-1) Submission (Report uploaded through Canvas) The report should include your entire code. your explanation for the various sections of your project code Focus more on explaining the following Your logic to randomly distribute the assigmed number of coins to the cells in the grid, the implementation of the dynamic programming algorithm to compute the optimal value for the coins collected, the sequence of cells that the robot shouild visit firom cell (0.0) to cell (n- 1. m-1) and the individual horizontal as well as vertical movements traced as purt of this path Alsa include a screenshot (as shown in a sample output displayed in the next page) of the output for the input values assigned to you 10
