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
R = 5 NEW_LINE C = 4 NEW_LINE intmin = - 10000000 NEW_LINE intmax = 10000000 NEW_LINE def isValid ( x , y1 , y2 ) : NEW_LINE INDENT return ( ( x >= 0 and x < R and y1 >= 0 and y1 < C and y2 >= 0 and y2 < C ) ) NEW_LINE DEDENT def getMaxUtil ( arr , mem , x , y1 , y2 ) : NEW_LINE INDENT if isValid ( x , y1 , y2 ) == False : NEW_LINE INDENT return intmin NEW_LINE DEDENT if x == R - 1 and y1 == 0 and y2 == C - 1 : NEW_LINE INDENT if y1 == y2 : NEW_LINE INDENT return arr [ x ] [ y1 ] NEW_LINE DEDENT else : NEW_LINE INDENT return arr [ x ] [ y1 ] + arr [ x ] [ y2 ] NEW_LINE DEDENT DEDENT if x == R - 1 : NEW_LINE INDENT return intmin NEW_LINE DEDENT if mem [ x ] [ y1 ] [ y2 ] != - 1 : NEW_LINE INDENT return mem [ x ] [ y1 ] [ y2 ] NEW_LINE DEDENT ans = intmin NEW_LINE temp = 0 NEW_LINE if y1 == y2 : NEW_LINE INDENT temp = arr [ x ] [ y1 ] NEW_LINE DEDENT else : NEW_LINE INDENT temp = arr [ x ] [ y1 ] + arr [ x ] [ y2 ] NEW_LINE DEDENT ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 - 1 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 + 1 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 , y2 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 - 1 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 - 1 , y2 + 1 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 - 1 ) ) NEW_LINE ans = max ( ans , temp + getMaxUtil ( arr , mem , x + 1 , y1 + 1 , y2 + 1 ) ) NEW_LINE mem [ x ] [ y1 ] [ y2 ] = ans NEW_LINE return ans NEW_LINE DEDENT def geMaxCollection ( arr ) : NEW_LINE INDENT mem = [ [ [ - 1 for i in range ( C ) ] for i in range ( C ) ] for i in range ( R ) ] NEW_LINE return getMaxUtil ( arr , mem , 0 , 0 , C - 1 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ 3 , 6 , 8 , 2 ] , [ 5 , 2 , 4 , 3 ] , [ 1 , 1 , 20 , 10 ] , [ 1 , 1 , 20 , 10 ] , [ 1 , 1 , 20 , 10 ] , ] NEW_LINE print ( ' Maximum ▁ collection ▁ is ▁ ' , geMaxCollection ( arr ) ) NEW_LINE DEDENT