Collect maximum points in a grid using two traversals | A Memoization based program to find maximum collection using two traversals of a grid ; checks whether a given input is valid or not ; Driver function to collect max value ; if P1 or P2 is at an invalid cell ; if both traversals reach their destinations ; If both traversals are at last row but not at their destination ; If subproblem is already solved ; Initialize answer for this subproblem ; this variable is used to store gain of current cell ( s ) ; Recur for all possible cases , then store and return the one with max value ; This is mainly a wrapper over recursive function getMaxUtil ( ) . This function creates a table for memoization and calls getMaxUtil ( ) ; Create a memoization table and initialize all entries as - 1 ; Calculation maximum value using memoization based function getMaxUtil ( ) ; Driver program to test above functions
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define R  5 NEW_LINE #define C  4 NEW_LINE bool isValid ( int x , int y1 , int y2 ) { return ( x >= 0 && x < R && y1 >= 0 && y1 < C && y2 >= 0 && y2 < C ) ; } int getMaxUtil ( int arr [ R ] [ C ] , int mem [ R ] [ C ] [ C ] , int x , int y1 , int y2 ) { if ( ! isValid ( x , y1 , y2 ) ) return INT_MIN ; if ( x == R - 1 && y1 == 0 && y2 == C - 1 ) return ( y1 == y2 ) ? arr [ x ] [ y1 ] : arr [ x ] [ y1 ] + arr [ x ] [ y2 ] ; if ( x == R - 1 ) return INT_MIN ; if ( mem [ x ] [ y1 ] [ y2 ] != -1 ) return mem [ x ] [ y1 ] [ y2 ] ; int ans = INT_MIN ; int temp = ( y1 == y2 ) ? arr [ x ] [ y1 ] : arr [ x ] [ y1 ] + arr [ x ] [ y2 ] ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 - 1 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 + 1 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 - 1 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 + 1 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 - 1 ) ) ; ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 + 1 ) ) ; return ( mem [ x ] [ y1 ] [ y2 ] = ans ) ; } int geMaxCollection ( int arr [ R ] [ C ] ) { int mem [ R ] [ C ] [ C ] ; memset ( mem , -1 , sizeof ( mem ) ) ; return getMaxUtil ( arr , mem , 0 , 0 , C - 1 ) ; } int main ( ) { int arr [ R ] [ C ] = { { 3 , 6 , 8 , 2 } , { 5 , 2 , 4 , 3 } , { 1 , 1 , 20 , 10 } , { 1 , 1 , 20 , 10 } , { 1 , 1 , 20 , 10 } , } ; cout << " Maximum ▁ collection ▁ is ▁ " << geMaxCollection ( arr ) ; return 0 ; }