Collect maximum coins before hitting a dead end | A Naive Recursive C ++ 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 ; Down ; Ahead in right ; Direction is left Get the maximum of two cases when you are facing left in this cell Down ; Ahead in left ; Driver program to test above function ; As per the question initial cell is ( 0 , 0 ) and direction is right
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define R  5 NEW_LINE #define C  5 NEW_LINE bool isValid ( int i , int j ) { return ( i >= 0 && i < R && j >= 0 && j < C ) ; } int maxCoinsRec ( char arr [ R ] [ C ] , int i , int j , int dir ) { if ( isValid ( i , j ) == false arr [ i ] [ j ] == ' # ' ) return 0 ; int result = ( arr [ i ] [ j ] == ' C ' ) ? 1 : 0 ; if ( dir == 1 ) return result + max ( maxCoinsRec ( arr , i + 1 , j , 0 ) , maxCoinsRec ( arr , i , j + 1 , 1 ) ) ; return result + max ( maxCoinsRec ( arr , i + 1 , j , 1 ) , maxCoinsRec ( arr , i , j - 1 , 0 ) ) ; } int main ( ) { char arr [ R ] [ C ] = { { ' E ' , ' C ' , ' C ' , ' C ' , ' C ' } , { ' C ' , ' # ' , ' C ' , ' # ' , ' E ' } , { ' # ' , ' C ' , ' C ' , ' # ' , ' C ' } , { ' C ' , ' E ' , ' E ' , ' C ' , ' E ' } , { ' C ' , ' E ' , ' # ' , ' C ' , ' E ' } } ; cout << " Maximum ▁ number ▁ of ▁ collected ▁ coins ▁ is ▁ " << maxCoinsRec ( arr , 0 , 0 , 1 ) ; return 0 ; }