Given a character matrix where every cell has one of the following values.
'C' --> This cell has coin '#' --> This cell is a blocking cell. We can not go anywhere from this. 'E' --> This cell is empty. We don't get a coin, but we can move from here.
Initial position is cell (0, 0) and initial direction is right.
Following are rules for movements across cells.
If face is Right, then we can move to below cells
- Move one step ahead, i.e., cell (i, j+1) and direction remains right.
- Move one step down and face left, i.e., cell (i+1, j) and direction becomes left.
If face is Left, then we can move to below cells
- Move one step ahead, i.e., cell (i, j-1) and direction remains left.
Move one step down and face right, i.e., cell (i+1, j) and direction becomes right.
Final position can be anywhere and final direction can also be anything. The target is to collect maximum coins.
Example:
Â
We strongly recommend you to minimize your browser and try this yourself first.
The above problem can be recursively defined as below:
maxCoins(i, j, d): Â Maximum number of coins that can beÂ
          collected if we begin at cell (i, j)
          and direction d.
          d can be either 0 (left) or 1 (right) // If this is a blocking cell, return 0. isValid() checks
 // if i and j are valid row and column indexes.
 If (arr[i][j] == ‘#’ or isValid(i, j) == false)
   return 0 // Initialize result
 If (arr[i][j] == ‘C’)
   result = 1;
 ElseÂ
   result = 0; If (d == 0) // Left directionÂ
   return result +  max(maxCoins(i+1, j, 1),  // Down
              maxCoins(i, j-1, 0)); // Ahead in left If (d == 1) // Right directionÂ
   return result +  max(maxCoins(i+1, j, 1),  // Down
              maxCoins(i, j+1, 0)); // Ahead in right
Below is C++ implementation of above recursive algorithm.
C++
// A Naive Recursive C++ program to find maximum number of coins // that can be collected before hitting a dead end #include<bits/stdc++.h> using namespace std; #define R 5 #define C 5 Â
// to check whether current cell is out of the grid or not bool isValid( int i, int j) { Â Â Â Â return (i >=0 && i < R && j >=0 && j < C); } Â
// dir = 0 for left, dir = 1 for facing right. This function returns // number of maximum coins that can be collected starting from (i, j). int maxCoinsRec( char arr[R][C], int i, int j, int dir) {     // If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) == false || arr[i][j] == '#' )         return 0; Â
    // Check if this cell contains the coin 'C' or if its empty 'E'.     int result = (arr[i][j] == 'C' )? 1: 0; Â
    // Get the maximum of two cases when you are facing right in this cell     if (dir == 1) // Direction is right     return result + max(maxCoinsRec(arr, i+1, j, 0),    // Down                             maxCoinsRec(arr, i, j+1, 1)); // Ahead in right Â
    // Direction is left     // Get the maximum of two cases when you are facing left in this cell     return result + max(maxCoinsRec(arr, i+1, j, 1), // Down                         maxCoinsRec(arr, i, j-1, 0)); // Ahead in left } Â
// Driver program to test above function 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' } Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â }; Â
// As per the question initial cell is (0, 0) and direction is     // right     cout << "Maximum number of collected coins is "         << maxCoinsRec(arr, 0, 0, 1); Â
    return 0; } |
Java
// A Naive Recursive Java program to find maximum number of // coins that can be collected before hitting a dead end import java.util.*; Â
public class Main { Â
  static int R = 5 ;   static int C = 5 ; Â
  // Driver program to test above function   public static void main(String[] args)   {     char arr[][] = { { 'E' , 'C' , 'C' , 'C' , 'C' },                     { 'C' , '#' , 'C' , '#' , 'E' },                     { '#' , 'C' , 'C' , '#' , 'C' },                     { 'C' , 'E' , 'E' , 'C' , 'E' },                     { 'C' , 'E' , '#' , 'C' , 'E' } }; Â
    // As per the question initial cell is (0, 0) and     // direction is right     System.out.println(       "Maximum number of collected coins is "       + maxCoinsRec(arr, 0 , 0 , 1 ));   }   // to check whether current cell is out of the grid or   // not   static boolean isValid( int i, int j)   {     return (i >= 0 && i < R && j >= 0 && j < C);   } Â
  // dir = 0 for left, dir = 1 for facing right. This   // function returns   // number of maximum coins that can be collected   // starting from (i, j).   static int maxCoinsRec( char arr[][], int i, int j,                          int dir)   {     // If this is a invalid cell or if cell is a     // blocking cell     if (isValid(i, j) == false || arr[i][j] == '#' ) {       return 0 ;     } Â
    // Check if this cell contains the coin 'C' or if     // its empty 'E'.     int result = (arr[i][j] == 'C' ) ? 1 : 0 ; Â
    // Get the maximum of two cases when you are facing     // right in this cell     if (dir == 1 ) { // Direction is right       return result         + Math.max(         maxCoinsRec(arr, i + 1 , j, 0 ), // Down         maxCoinsRec(arr, i, j + 1 ,                     1 )); // Ahead in right     } Â
    // Direction is left     // Get the maximum of two cases when you are facing     // left in this cell     else {       return result         + Math.max(         maxCoinsRec(arr, i + 1 , j, 1 ), // Down         maxCoinsRec(arr, i, j - 1 ,                     0 )); // Ahead in left     }   } } Â
// This code is contributed by tapeshdua420. |
Python3
# A Naive Recursive Python 3 program to # find maximum number of coins # that can be collected before hitting a dead end R = 5 C = 5 Â
# to check whether current cell is out of the grid or not def isValid( i, j): Â
    return (i > = 0 and i < R and j > = 0 and j < C) Â
Â
# dir = 0 for left, dir = 1 for facing right. # This function returns # number of maximum coins that can be collected # starting from (i, j). def maxCoinsRec(arr, i, j, dir ): Â
    # If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) = = False or arr[i][j] = = '#' ):         return 0 Â
    # Check if this cell contains the coin 'C' or if its empty 'E'.     if (arr[i][j] = = 'C' ):         result = 1     else :         result = 0 Â
    # Get the maximum of two cases when you are facing right in this cell     if ( dir = = 1 ):              # Direction is right         return (result + max (maxCoinsRec(arr, i + 1 , j, 0 ),             maxCoinsRec(arr, i, j + 1 , 1 ))) Â
    # Direction is left     # Get the maximum of two cases when you are facing left in this cell     return (result + max (maxCoinsRec(arr, i + 1 , j, 1 ),         maxCoinsRec(arr, i, j - 1 , 0 ))) Â
Â
# Driver program to test above function if __name__ = = '__main__' : Â Â Â Â arr = [ [ 'E' , 'C' , 'C' , 'C' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , '#' , 'C' , '#' , 'E' ], Â Â Â Â Â Â Â Â [ '#' , 'C' , 'C' , '#' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , 'E' , 'C' , 'E' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , '#' , 'C' , 'E' ] ] Â
    # As per the question initial cell is (0, 0) and direction is     # right     print ( "Maximum number of collected coins is " , maxCoinsRec(arr, 0 , 0 , 1 )) Â
# this code is contributed by ash264 |
C#
// A Naive Recursive C# program to find maximum number of // coins that can be collected before hitting a dead end using System; Â
class Program { Â
    static int R = 5;     static int C = 5; Â
    public static void Main( string [] args)     {         // Driver program to test above function         char [, ] arr             = new char [, ] { { 'E' , 'C' , 'C' , 'C' , 'C' },                              { 'C' , '#' , 'C' , '#' , 'E' },                              { '#' , 'C' , 'C' , '#' , 'C' },                              { 'C' , 'E' , 'E' , 'C' , 'E' },                              { 'C' , 'E' , '#' , 'C' , 'E' } }; Â
        // As per the question initial cell is (0, 0) and         // direction is right         Console.WriteLine(             "Maximum number of collected coins is "             + maxCoinsRec(arr, 0, 0, 1));     } Â
    // to check whether current cell is out of the grid or     // not     public static bool isValid( int i, int j)     { Â
        return (i >= 0 && i < R && j >= 0 && j < C);     } Â
    // dir = 0 for left, dir = 1 for facing right. This     // function returns     // number of maximum coins that can be collected     // starting from (i, j).     public static int maxCoinsRec( char [, ] arr, int i,                                   int j, int dir)     { Â
        // If this is a invalid cell or if cell is a         // blocking cell         if (isValid(i, j) == false || arr[i, j] == '#' )             return 0; Â
        // Check if this cell contains the coin 'C' or if         // its empty 'E'.         int result = (arr[i, j] == 'C' ) ? 1 : 0; Â
        // Get the maximum of two cases when you are facing         // right in this cell         if (dir == 1) // Direction is right             return result                 + Math.Max(                     maxCoinsRec(arr, i + 1, j, 0), // Down                     maxCoinsRec(arr, i, j + 1,                                 1)); // Ahead in right         // Direction is left         // Get the maximum of two cases when you are facing         // left in this cell         else             return result                 + Math.Max(                     maxCoinsRec(arr, i + 1, j, 1), // Down                     maxCoinsRec(arr, i, j - 1,                                 0)); // Ahead in left     } } Â
// This code is contributed by tapeshdua420. |
Javascript
<script> Â
// A Naive Recursive JavaScript program to find maximum number of coins // that can be collected before hitting a dead end Â
const R = 5 const C = 5 Â
// to check whether current cell is out of the grid or not function isValid(i, j) { Â Â Â Â return (i >=0 && i < R && j >=0 && j < C); } Â
// dir = 0 for left, dir = 1 for facing right. This function returns // number of maximum coins that can be collected starting from (i, j). function maxCoinsRec(arr,i,j,dir) {     // If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) == false || arr[i][j] == '#' )         return 0; Â
    // Check if this cell contains the coin 'C' or if its empty 'E'.     let result = (arr[i][j] == 'C' )? 1: 0; Â
    // Get the maximum of two cases when you are facing right in this cell     if (dir == 1) // Direction is right     return result + Math.max(maxCoinsRec(arr, i+1, j, 0),    // Down                             maxCoinsRec(arr, i, j+1, 1)); // Ahead in right Â
    // Direction is left     // Get the maximum of two cases when you are facing left in this cell     return result + Math.max(maxCoinsRec(arr, i+1, j, 1), // Down                         maxCoinsRec(arr, i, j-1, 0)); // Ahead in left } Â
// Driver program to test above function Â
let arr = [ [ 'E' , 'C' , 'C' , 'C' , 'C' ], Â Â Â Â Â Â Â Â Â Â Â Â [ 'C' , '#' , 'C' , '#' , 'E' ], Â Â Â Â Â Â Â Â Â Â Â Â [ '#' , 'C' , 'C' , '#' , 'C' ], Â Â Â Â Â Â Â Â Â Â Â Â [ 'C' , 'E' , 'E' , 'C' , 'E' ], Â Â Â Â Â Â Â Â Â Â Â Â [ 'C' , 'E' , '#' , 'C' , 'E' ] Â Â Â Â Â Â Â Â Â Â ]; Â
// As per the question initial cell is (0, 0) and direction is // right document.write( "Maximum number of collected coins is " + maxCoinsRec(arr, 0, 0, 1), "</br>" ); Â
// This code is contributed by shinjanpatra Â
</script> |
Maximum number of collected coins is 8
Time Complexity: O(2^(R+C)), where R and C are the number of rows and columns in the grid, respectively. This is because in the worst case, we need to explore all possible paths in the grid, which can be as many as 2^(R+C).
Auxiliary Space: O(R+C), which corresponds to the maximum depth of the recursive call stack.
We can solve this problem in Polynomial Time using Dynamic Programming. The idea is to use a 3 dimensional table dp[R][C][k] where R is number of rows, C is number of columns and d is direction. Below is Dynamic Programming based C++ implementation.
C++
// A Dynamic Programming based C++ program to find maximum // number of coins that can be collected before hitting a // dead end #include<bits/stdc++.h> using namespace std; #define R 5 #define C 5 Â
// to check whether current cell is out of the grid or not bool isValid( int i, int j) { Â Â Â Â return (i >=0 && i < R && j >=0 && j < C); } Â
// dir = 0 for left, dir = 1 for right. This function returns // number of maximum coins that can be collected starting from // (i, j). int maxCoinsUtil( char arr[R][C], int i, int j, int dir,                 int dp[R][C][2]) {     // If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) == false || arr[i][j] == '#' )         return 0; Â
    // If this subproblem is already solved than return the     // already evaluated answer.     if (dp[i][j][dir] != -1)     return dp[i][j][dir]; Â
    // Check if this cell contains the coin 'C' or if its 'E'.     dp[i][j][dir] = (arr[i][j] == 'C' )? 1: 0; Â
    // Get the maximum of two cases when you are facing right     // in this cell     if (dir == 1) // Direction is right     dp[i][j][dir] += max(maxCoinsUtil(arr, i+1, j, 0, dp), // Down                             maxCoinsUtil(arr, i, j+1, 1, dp)); // Ahead in right Â
    // Get the maximum of two cases when you are facing left     // in this cell     if (dir == 0) // Direction is left     dp[i][j][dir] += max(maxCoinsUtil(arr, i+1, j, 1, dp), // Down                             maxCoinsUtil(arr, i, j-1, 0, dp)); // Ahead in left Â
    // return the answer     return dp[i][j][dir]; } Â
// This function mainly creates a lookup table and calls // maxCoinsUtil() int maxCoins( char arr[R][C]) { Â Â Â Â // Create lookup table and initialize all values as -1 Â Â Â Â int dp[R][C][2]; Â Â Â Â memset (dp, -1, sizeof dp); Â
    // As per the question initial cell is (0, 0) and direction     // is right     return maxCoinsUtil(arr, 0, 0, 1, dp); } Â
// Driver program to test above function 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 "         << maxCoins(arr); Â
    return 0; } |
Java
// A Dynamic Programming based Java program to find maximum // number of coins that can be collected before hitting a // dead end import java.util.*; Â
public class Main { Â Â static int R = 5 ; Â Â static int C = 5 ; Â
  // Driver program to test above function   public static void main(String[] args)   {     char [][] arr = { { 'E' , 'C' , 'C' , 'C' , 'C' },                     { 'C' , '#' , 'C' , '#' , 'E' },                     { '#' , 'C' , 'C' , '#' , 'C' },                     { 'C' , 'E' , 'E' , 'C' , 'E' },                     { 'C' , 'E' , '#' , 'C' , 'E' } };     System.out.println(       "Maximum number of collected coins is "       + maxCoins(arr));   } Â
  // This function mainly creates a lookup table and calls   // maxCoinsUtil()   public static int maxCoins( char [][] arr)   {     // Create lookup table and initialize all values as     // -1     int [][][] dp = new int [ 5 ][ 5 ][ 2 ];     for ( int i = 0 ; i < 5 ; i++) {       for ( int j = 0 ; j < 5 ; j++) {         dp[i][j][ 0 ] = - 1 ;         dp[i][j][ 1 ] = - 1 ;       }     } Â
    // As per the question initial cell is (0, 0) and     // direction     // is right     return maxCoinsUtil(arr, 0 , 0 , 1 , dp);   } Â
  // to check whether current cell is out of the grid or   // not   public static boolean isValid( int i, int j)   {     return (i >= 0 && i < R && j >= 0 && j < C);   } Â
  // dir = 0 for left, dir = 1 for right. This function   // returns number of maximum coins that can be collected   // starting from (i, j).   public static int maxCoinsUtil( char [][] arr, int i,                                  int j, int dir,                                  int [][][] dp)   {     // If this is a invalid cell or if cell is a     // blocking cell     if (!isValid(i, j) || arr[i][j] == '#' ) {       return 0 ;     } Â
    // If this subproblem is already solved than return     // the already evaluated answer.     if (dp[i][j][dir] != - 1 ) {       return dp[i][j][dir];     }     // Check if this cell contains the coin 'C' or if     // its 'E'.     dp[i][j][dir] = (arr[i][j] == 'C' ) ? 1 : 0 ; Â
    // Get the maximum of two cases when you are facing     // right in this cell     if (dir == 1 ) { // Direction is right       dp[i][j][dir] += Math.max(         maxCoinsUtil(arr, i + 1 , j, 0 , dp), // Down         maxCoinsUtil(arr, i, j + 1 , 1 ,                      dp)); // Ahead in right     }     // Get the maximum of two cases when you are facing     // left     // in this cell     if (dir == 0 ) { // Direction is left       dp[i][j][dir] += Math.max(         maxCoinsUtil(arr, i + 1 , j, 1 , dp), // Down         maxCoinsUtil(arr, i, j - 1 , 0 ,                      dp)); // Ahead in left     } Â
    // return the answer     return dp[i][j][dir];   } } Â
// This code is contributed by Tapesh(tapeshdua420) |
Python3
# A Dynamic Programming based C++ program to find maximum # number of coins that can be collected before hitting a # dead end Â
R = 5 C = 5 Â
# to check whether current cell is out of the grid or not def isValid(i, j): Â Â Â Â return (i > = 0 and i < R and j > = 0 and j < C) Â
Â
# dir = 0 for left, dir = 1 for right. This function returns # number of maximum coins that can be collected starting from # (i, j). def maxCoinsUtil(arr,i,j, dir ,dp): Â
    # If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) = = False or arr[i][j] = = '#' ):         return 0 Â
    # If this subproblem is already solved than return the     # already evaluated answer.     if (dp[i][j][ dir ] ! = - 1 ):         return dp[i][j][ dir ] Â
    # Check if this cell contains the coin 'C' or if its 'E'.     dp[i][j][ dir ] = 1 if (arr[i][j] = = 'C' ) else 0 Â
    # Get the maximum of two cases when you are facing right     # in this cell     if ( dir = = 1 ): # Direction is right         dp[i][j][ dir ] + = max (maxCoinsUtil(arr, i + 1 , j, 0 , dp), # Down                             maxCoinsUtil(arr, i, j + 1 , 1 , dp)) # Ahead in right Â
    # Get the maximum of two cases when you are facing left     # in this cell     if ( dir = = 0 ): # Direction is left         dp[i][j][ dir ] + = max (maxCoinsUtil(arr, i + 1 , j, 1 , dp), # Down                             maxCoinsUtil(arr, i, j - 1 , 0 , dp)) # Ahead in left Â
    # return the answer     return dp[i][j][ dir ] Â
# This function mainly creates a lookup table and calls # maxCoinsUtil() def maxCoins(arr): Â
    # Create lookup table and initialize all values as -1     dp = [[[ - 1 for i in range ( 2 )] for j in range (C)] for k in range (R)] Â
    # As per the question initial cell is (0, 0) and direction     # is right     return maxCoinsUtil(arr, 0 , 0 , 1 , dp) Â
# Driver program to test above function Â
arr = [ [ 'E' , 'C' , 'C' , 'C' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , '#' , 'C' , '#' , 'E' ], Â Â Â Â Â Â Â Â [ '#' , 'C' , 'C' , '#' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , 'E' , 'C' , 'E' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , '#' , 'C' , 'E' ] Â Â Â Â Â Â ] Â
print (f "Maximum number of collected coins is {maxCoins(arr)}" ) Â
# This code is contributed by shinjanpatra |
C#
// A Dynamic Programming based C# program to find maximum // number of coins that can be collected before hitting a // dead end using System; Â
class Program { Â Â Â Â static int R = 5; Â Â Â Â static int C = 5; Â
    // Driver program to test above function     public static void Main(String[] args)     {         char [, ] arr = { { 'E' , 'C' , 'C' , 'C' , 'C' },                          { 'C' , '#' , 'C' , '#' , 'E' },                          { '#' , 'C' , 'C' , '#' , 'C' },                          { 'C' , 'E' , 'E' , 'C' , 'E' },                          { 'C' , 'E' , '#' , 'C' , 'E' } }; Â
        Console.WriteLine(             "Maximum number of collected coins is "             + maxCoins(arr));     } Â
    // This function mainly creates a lookup table and calls     // maxCoinsUtil()     public static int maxCoins( char [, ] arr)     {         // Create lookup table and initialize all values as         // -1         int [, , ] dp = new int [5, 5, 2];         for ( int i = 0; i < 5; i++)             for ( int j = 0; j < 5; j++) {                 dp[i, j, 0] = -1;                 dp[i, j, 1] = -1;             } Â
        // As per the question initial cell is (0, 0) and         // direction is right         return maxCoinsUtil(arr, 0, 0, 1, dp);     } Â
    // to check whether current cell is out of the grid or     // not     public static bool isValid( int i, int j)     {         return (i >= 0 && i < R && j >= 0 && j < C);     } Â
    // dir = 0 for left, dir = 1 for right. This function     // returns number of maximum coins that can be collected     // starting from (i, j).     public static int maxCoinsUtil( char [, ] arr, int i,                                    int j, int dir,                                    int [, , ] dp)     { Â
        // If this is a invalid cell or if cell is a         // blocking cell         if (!isValid(i, j) || arr[i, j] == '#' )             return 0; Â
        // If this subproblem is already solved than return         // the already evaluated answer.         if (dp[i, j, dir] != -1)             return dp[i, j, dir];         ; Â
        // Check if this cell contains the coin ‘C’ or if         // its ‘E’.         dp[i, j, dir] = (arr[i, j] == 'C' ) ? 1 : 0; Â
        // Get the maximum of two cases when you are facing         // right in this cell         if (dir == 1) { // Direction is right             dp[i, j, dir] += Math.Max(                 maxCoinsUtil(arr, i + 1, j, 0, dp), // Down                 maxCoinsUtil(arr, i, j + 1, 1,                              dp)); // Ahead in right         } Â
        // Get the maximum of two cases when you are facing         // left in this cell         if (dir == 0) { // Direction is left             dp[i, j, dir] += Math.Max(                 maxCoinsUtil(arr, i + 1, j, 1, dp), // Down                 maxCoinsUtil(arr, i, j - 1, 0,                              dp)); // Ahead in left         }         return dp[i, j, dir];     } } Â
// This code is contributed by Tapesh(tapeshdua420) |
Javascript
<script> Â
// A Dynamic Programming based JavaScript program to find maximum // number of coins that can be collected before hitting a // dead end Â
let R = 5 let C = 5 Â
// to check whether current cell is out of the grid or not function isValid(i, j){ Â Â Â Â return (i >=0 && i < R && j >=0 && j < C) } Â
Â
// dir = 0 for left, dir = 1 for right. This function returns // number of maximum coins that can be collected starting from // (i, j). function maxCoinsUtil(arr,i,j,dir,dp){ Â
    // If this is a invalid cell or if cell is a blocking cell     if (isValid(i,j) == false || arr[i][j] == '#' )         return 0 Â
    // If this subproblem is already solved than return the     // already evaluated answer.     if (dp[i][j][dir] != -1)         return dp[i][j][dir] Â
    // Check if this cell contains the coin 'C' or if its 'E'.     if (arr[i][j] == 'C' )         dp[i][j][dir] = 1     else dp[i][j][dir] = 0 Â
    // Get the maximum of two cases when you are facing right     // in this cell     if (dir == 1){ // Direction is right         dp[i][j][dir] += Math.max(maxCoinsUtil(arr, i+1, j, 0, dp), // Down                             maxCoinsUtil(arr, i, j+1, 1, dp)) // Ahead in right     } Â
    // Get the maximum of two cases when you are facing left     // in this cell     if (dir == 0) // Direction is left         dp[i][j][dir] += Math.max(maxCoinsUtil(arr, i+1, j, 1, dp), // Down                             maxCoinsUtil(arr, i, j-1, 0, dp)) // Ahead in left Â
    // return the answer     return dp[i][j][dir] } Â
// This function mainly creates a lookup table and calls // maxCoinsUtil() function maxCoins(arr){ Â
    // Create lookup table and initialize all values as -1     let dp = new Array(R).fill(0).map(()=> new Array(C).fill(0).map(()=> new Array(2).fill(-1))) Â
    // As per the question initial cell is (0, 0) and direction     // is right     return maxCoinsUtil(arr, 0, 0, 1, dp) } Â
// Driver program to test above function Â
let arr = [ [ 'E' , 'C' , 'C' , 'C' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , '#' , 'C' , '#' , 'E' ], Â Â Â Â Â Â Â Â [ '#' , 'C' , 'C' , '#' , 'C' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , 'E' , 'C' , 'E' ], Â Â Â Â Â Â Â Â [ 'C' , 'E' , '#' , 'C' , 'E' ] Â Â Â Â Â Â ] Â
document.write(`Maximum number of collected coins is ${maxCoins(arr)}`, "</br>" ) Â
// This code is contributed by shinjanpatra Â
</script> |
Maximum number of collected coins is 8
Time Complexity: O(R x C x d). Since d is 2, time complexity can be written as O(R x C).
Auxiliary Space: O(R x C x 2), We are using a 3D array of size R*C*2 to store the results of the subproblems, where R and C are the number of rows and columns of the grid.
Thanks to Gaurav Ahirwar for suggesting above solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!