3. CHALLENGE: Consider an 8x8 checkerboard that has a dollar amount printed on e

Question

3. CHALLENGE: Consider an 8x8 checkerboard that has a dollar amount printed on each of its squares:

Imagine you can place a checker on the board anywhere you want and then move it across the board with standard diagonal moves. Once you reach the other side, you are finished. You will collect an amount of money equal to the sum of the values written on the squares that your

checker traveled over. Develop a recursive algorithm that will compute the maximum amount you can collect.

Hints: call the function maxValue. The function should accept the board, and a row and column number as input, and return the maximum dollar value possible by moving the piece to the far side of the board. In other words, function value = maxValue(board, row, col)

Assume that row 8 is the bottom of the board and row 1 is the destination. The general case will involve invoking maxValue on the square found by moving up (subtract 1 from row) and left ( subtract 1 from column) and moving up and right (add + to column) from the current row and column, and simply returning the larger of the two. You'll need to add a base case (row = 1) and figure out how to handle the edges so you don't fall off the board.

Here are some additional hints:

Base Case 1: row is 1. Just return the value of the board[row][col] (no further recursive calls)

Base Case 2: col is either less than 1 or greater than 8 (fell off board). Just return zero (no

further recursive calls)

General Case: set left equal to the maxValue (recursive call) of the cell above and to the left of

board[row][col], and set right to the maxValue (recursive call) of the cell above and to the right of board[row][col]. Add whichever is bigger (left or right) to the value at board[row][col] and return this value.

Explanation / Answer

//check
#include <iostream>
using namespace std;
int maxValue(int board[][8], int row, int col)
{
  
   static int max=0;
if(row==1)
{
    return board[row][col];
}
else if(col<1 || col>8)
{
    return 0;
}
else
{
    int left=maxValue(board,row,col-1);
    int right=maxValue(board,row,col+1);
if(left > right)
{
   col--;
   return left;
   }
   else if(right>left)
   {
      col++;
       return right;  
   }
   row--;
}
}
int main()
{
   int row, col;
   int board[][8] = {{6,4,7,4,8,3,6,7},
{   9,1,4,7,3,6,8,6 },
{9,1,4,7,3,6,8,6},
{1,8,6,6,8,4,8,3},
{7,3,7,4,4,1,5,9 },
{1,6,3,2,1,4,3,3},
{5,3,8,4,2,6,7,9},
{6,4,3,8,7,1,2,4}};
cout<<endl<<"Enter a position <row,col>: ";
cin>>row>>col;
int max_value=maxValue(board,row,col);
cout<<endl<<"Game Over. You earned $"<<max_value;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.