Collect maximum coins before hitting a dead end - GeeksforGeeks
Given a character matrix where every cell has one of the following values.
Following are rules for movements across cells.
If face is Right, then we can move to below cells
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.
Read full article from Collect maximum coins before hitting a dead end - GeeksforGeeks
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, j-1) and direction becomes right.
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.
Time Complexity of above solution is O(R x C x d). Since d is 2, time complexity can be written as O(R x 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 rught // 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);}// to check whether current cell is out of the grid or notbool 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}