Collect Maximum Coins Before Hitting a Dead End

Given a character grid of size R x C containing:

• 'C': A cell containing a coin.
• 'E': An empty cell.
• '#': A blocking wall/obstacle cell (cannot be visited).

We start at cell (0, 0) facing Right. We can only move according to specific direction-based rules. The goal is to collect the maximum number of coins before hitting a dead end (a situation where no further moves are possible).

Movement Rules

• If facing Right (dir = 1):
  • Move ahead: Go to (i, j + 1) (direction remains Right).
  • Move down: Go to (i + 1, j) (direction changes to Left).
• If facing Left (dir = 0):
  • Move ahead: Go to (i, j - 1) (direction remains Left).
  • Move down: Go to (i + 1, j) (direction changes to Right).

Examples

Example

Consider the following grid:

E C C
C # C
C C E

• Path:
  1. Start (0, 0) facing Right. Cell is empty.
  2. Move Right to (0, 1). Collect coin (C).
  3. Move Right to (0, 2). Collect coin (C).
  4. From (0, 2) facing Right, moving Right goes out of bounds. Move Down to (1, 2). Direction changes to Left. Collect coin (C).
  5. From (1, 2) facing Left, move Left to (1, 1) (blocked by '#'). Move Down to (2, 2). Direction changes to Right. Cell is empty.
• Total Coins Collected: 3

Dynamic Programming State & Transition

Since the direction affects future valid moves, we use a 3D state representation: dp[i][j][dir] represents the maximum coins collected starting from cell (i, j) with direction dir (where dir = 1 for Right, and dir = 0 for Left).

Transition Formulas

• If cell is invalid (out of bounds or '#'): helper(i, j, dir) = 0
• If facing Right (dir === 1): helper(i, j, 1) = coin + max(helper(i, j + 1, 1), helper(i + 1, j, 0))
• If facing Left (dir === 0): helper(i, j, 0) = coin + max(helper(i, j - 1, 0), helper(i + 1, j, 1))

JavaScript Code Implementation

function maxCoins(grid) {
    const R = grid.length;
    if (R === 0) return 0;
    const C = grid[0].length;
 
    // Create a 3D memoization array initialized to -1
    // memo[R][C][2]
    const memo = Array.from({ length: R }, () =>
        Array.from({ length: C }, () => new Array(2).fill(-1))
    );
 
    function helper(i, j, dir) {
        // Base case: If out of bounds or current cell is a wall/obstacle
        if (i < 0 || i >= R || j < 0 || j >= C || grid[i][j] === '#') {
            return 0;
        }
 
        // Return already calculated value
        if (memo[i][j][dir] !== -1) {
            return memo[i][j][dir];
        }
 
        // Check if there is a coin in the current cell
        const coin = (grid[i][j] === 'C') ? 1 : 0;
 
        let path1 = 0;
        let path2 = 0;
 
        if (dir === 1) { // Facing Right
            path1 = helper(i, j + 1, 1); // Move Right (dir remains Right)
            path2 = helper(i + 1, j, 0); // Move Down (dir becomes Left)
        } else { // Facing Left
            path1 = helper(i, j - 1, 0); // Move Left (dir remains Left)
            path2 = helper(i + 1, j, 1); // Move Down (dir becomes Right)
        }
 
        // Store and return the result
        memo[i][j][dir] = coin + Math.max(path1, path2);
        return memo[i][j][dir];
    }
 
    // Start from top-left cell (0, 0) facing Right (1)
    return helper(0, 0, 1);
}
 
// Driver code
const grid = [
    ['E', 'C', 'C'],
    ['C', '#', 'C'],
    ['C', 'C', 'E']
];
 
console.log("Maximum coins collected:", maxCoins(grid));
// Output: Maximum coins collected: 3

Complexity Analysis

• Time Complexity: O(R * C)
  • There are $R \times C \times 2$ states. Each state does $O(1)$ work to compute.
• Space Complexity: O(R * C)
  • To store the 3D memoization array of size $R \times C \times 2$ and recursion stack.