Collect maximum coins before hitting a dead end | A Naive Recursive Python 3 program to find maximum number of coins that can be collected before hitting a dead end ; to check whether current cell is out of the grid or not ; dir = 0 for left , dir = 1 for facing right . This function returns number of maximum coins that can be collected starting from ( i , j ) . ; If this is a invalid cell or if cell is a blocking cell ; Check if this cell contains the coin ' C ' or if its empty ' E ' . ; Get the maximum of two cases when you are facing right in this cell ; Direction is right ; Direction is left Get the maximum of two cases when you are facing left in this cell ; Driver program to test above function ; As per the question initial cell is ( 0 , 0 ) and direction is right
R = 5 NEW_LINE C = 5 NEW_LINE def isValid ( i , j ) : NEW_LINE INDENT return ( i >= 0 and i < R and j >= 0 and j < C ) NEW_LINE DEDENT def maxCoinsRec ( arr , i , j , dir ) : NEW_LINE INDENT if ( isValid ( i , j ) == False or arr [ i ] [ j ] == ' # ' ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( arr [ i ] [ j ] == ' C ' ) : NEW_LINE INDENT result = 1 NEW_LINE DEDENT else : NEW_LINE INDENT result = 0 NEW_LINE DEDENT if ( dir == 1 ) : NEW_LINE INDENT return ( result + max ( maxCoinsRec ( arr , i + 1 , j , 0 ) , maxCoinsRec ( arr , i , j + 1 , 1 ) ) ) NEW_LINE DEDENT return ( result + max ( maxCoinsRec ( arr , i + 1 , j , 1 ) , maxCoinsRec ( arr , i , j - 1 , 0 ) ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ [ ' E ' , ' C ' , ' C ' , ' C ' , ' C ' ] , [ ' C ' , ' # ' , ' C ' , ' # ' , ' E ' ] , [ ' # ' , ' C ' , ' C ' , ' # ' , ' C ' ] , [ ' C ' , ' E ' , ' E ' , ' C ' , ' E ' ] , [ ' C ' , ' E ' , ' # ' , ' C ' , ' E ' ] ] NEW_LINE print ( " Maximum ▁ number ▁ of ▁ collected ▁ coins ▁ is ▁ " , maxCoinsRec ( arr , 0 , 0 , 1 ) ) NEW_LINE DEDENT