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.
Comments