JAVA PROGRAMMING - MUST BE DONE RECURSIVELY Problem 3: Picking up coins (1 playe
ID: 3730304 • Letter: J
Question
JAVA PROGRAMMING - MUST BE DONE RECURSIVELY
Problem 3: Picking up coins (1 player 2D) [20 points] Some coins are spread in the cells of an m x n board, one coin per cell. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell On each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it picks up that coin. Write a recursive function public static int collectCoins2D (int[] [ board, int row, int col) that takes a row and a col of the board as an argument and returns the the maximum number of coins the robot can collect by moving from that cell to the bottom right cell (row m-1 and col-n-1) In the example shown below if the robot starts at the upper left cell of the board (rowcol 0) it can collect 27 coins. (Can you see How?). You may assume that the board is always rectangular or square. If the row/col passed is outside the bounds of the board, return -1 1 9 8 0 6 1 2 8 3 For the above board collectCoins2d (board, 0, 0) must return 27 collectCoins2d (board, 2, 0)) must return 13 collectCoins2d (board, 1, 1)) must return 17 collectCoins2d (board, 2, 2)) must return 3 collectCoins2d (board, 4, 2)) must return -1Explanation / Answer
public class CollectCoins {
static int Max(int a, int b)
{
return a > b ? a : b;
}
static int collectCoins2D(int[][] cost, int m, int n)
{
int cols = cost[0].length; // To find number of columns in a matrix
int rows = cost.length; // To find number fo rows in a matrix
if (n >= cols || m >= rows) // To check out off grid access
return -1;
else if (m == (rows - 1) && n == (cols - 1)) // To check right most cell in grid
return cost[m][n];
else {
// collectCoins2D(cost, m + 1, n)---> Moving Down
// collectCoins2D(cost, m, n + 1) ---> Moving Right
return cost[m][n] + Max(collectCoins2D(cost, m + 1, n), collectCoins2D(cost, m, n + 1));
}
}
public static void main(String[] argv) throws Exception {
int[][] board = new int[][] { { 1, 9, 8 }, { 0, 6, 1 }, { 2, 8, 3 }, { 4, 5, 6 } };
System.out.println(collectCoins2D(board, 0, 0));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.