Caută
  • oanaunciuleanu

Collect maximum points in a grid using two traversals in C++



Using a grid of cells that hold values, try to find the maximum number of points that can be summed by using two traversals. The first traversal starts from the top left corner, and end in the bottom left corner. The second traversal starts from the top right corner and end in the bottom right corner. You can move from one cell to the other in only three ways: down one cell, down one cell in a diagonal to the left, or down one cell in a diagonal to the right. If a cell is being visited by both traversals, then its value will be added to the sum only once.



// Maximum points in a grid using two traversals

#include<bits/stdc++.h>
using namespace std;

#define Rows 5
#define Columns 4

bool isValidInput(int X_Axis_BothTraversals, int Y_Axis_FirstTraversal, int y2)
{
    return (X_Axis_BothTraversals >= 0 && X_Axis_BothTraversals < Rows && Y_Axis_FirstTraversal >=0 && Y_Axis_FirstTraversal < Columns && y2 >= 0 && y2 < Columns);
}

// Driver function to collect max value
int getMaxValue(int startArray[Rows][Columns], int memorize[Rows][Columns][Columns], int X_Axis_BothTraversals, int Y_Axis_FirstTraversal, int Y_Axis_SecondTraversal)
{
    if (!isValidInput(X_Axis_BothTraversals, Y_Axis_FirstTraversal, Y_Axis_SecondTraversal))
    {
        return INT_MIN;
    }

    // if both traversals reach their destinations
    if (X_Axis_BothTraversals == Rows - 1 && Y_Axis_FirstTraversal == 0 && Y_Axis_SecondTraversal == Columns - 1)
    {
         return (Y_Axis_FirstTraversal == Y_Axis_SecondTraversal)? startArray[X_Axis_BothTraversals][Y_Axis_FirstTraversal]: startArray[X_Axis_BothTraversals][Y_Axis_FirstTraversal] + startArray[X_Axis_BothTraversals][Y_Axis_SecondTraversal];
    }

    // If both traversals are at last row but not at their destination
    if (X_Axis_BothTraversals == Rows - 1)
    {
        return INT_MIN;
    }

    // If subproblem is already solved
    if (memorize[X_Axis_BothTraversals][Y_Axis_FirstTraversal][Y_Axis_SecondTraversal] != -1)
    {
        return memorize[X_Axis_BothTraversals][Y_Axis_FirstTraversal][Y_Axis_SecondTraversal];
    }

    int answer = INT_MIN;

    // current cell
    int temporary = (Y_Axis_FirstTraversal == Y_Axis_SecondTraversal)? startArray[X_Axis_BothTraversals][Y_Axis_FirstTraversal]: startArray[X_Axis_BothTraversals][Y_Axis_FirstTraversal] + startArray[X_Axis_BothTraversals][Y_Axis_SecondTraversal];

    // return max value of all possible cases
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal, Y_Axis_SecondTraversal -1));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal, Y_Axis_SecondTraversal +1));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal, Y_Axis_SecondTraversal));

    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal -1, Y_Axis_SecondTraversal));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal -1, Y_Axis_SecondTraversal -1));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal -1, Y_Axis_SecondTraversal +1));

    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal +1, Y_Axis_SecondTraversal));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal +1, Y_Axis_SecondTraversal -1));
    answer = max(answer, temporary + getMaxValue(startArray, memorize, X_Axis_BothTraversals + 1, Y_Axis_FirstTraversal +1, Y_Axis_SecondTraversal +1));

    return (memorize[X_Axis_BothTraversals][Y_Axis_FirstTraversal][Y_Axis_SecondTraversal] = answer);
}

int geMaxCollectionValue(int startArray[Rows][Columns])
{
    // Set all entries with -1
    int memorize[Rows][Columns][Columns];
    memset(memorize, -1, sizeof(memorize));

    return getMaxValue(startArray, memorize, 0, 0, Columns - 1);
}

// Driver program to test above functions
int main()
{
    int startArray[Rows][Columns] = {{1, 2, 3, 4},
                                     {5, 6, 7, 8},
                                     {9, 10, 11, 12},
                                     {13, 14, 15, 16},
                                     {17, 18, 19, 20}
                                    };
    int maxValue = geMaxCollectionValue(startArray);
    cout << "The maximum value of points from the two traversals is " << maxValue;
    return 0;
}

The   maximum value of points from the two traversals is 109.

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now