Lesson

13.12Path with Maximum Gold

Problem Statement

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, where 0 indicates an empty cell.

A rat is placed at position (0, 0) and aims to reach the destination at position (m-1, n-1). The rat can move in four possible directions:

'U' (Up)
'D' (Down)
'L' (Left)
'R' (Right)

Conditions:

Collecting Gold: Every time the rat is located in a cell, it collects all the gold in that cell.
Movement Constraints:
- The rat can move one step to the left, right, up, or down.
- The rat cannot visit the same cell more than once in a single path.
- The rat cannot move to a cell with 0 gold.
- The rat can start and stop collecting gold from any position in the grid that has some gold.
Blocked Source: If the source cell (0, 0) is 0, the rat cannot move to any other cell.

Task:
Find the maximum amount of gold the rat can collect by traversing the grid from the source to the destination under the given conditions.

Return:
An integer representing the maximum amount of gold the rat can collect. If no path exists, return 0.

Example Inputs

Example 1:

Example 2:

Example 3:

Approach

To find the maximum amount of gold the rat can collect, we can use a recursive backtracking approach. The key idea is to explore all possible paths from each cell that contains gold, keeping track of the total gold collected along the way, and ensuring that the rat does not revisit any cell in a single path.

Steps

Initialize:
- Create a variable maxGold to keep track of the maximum gold collected.
- Iterate through each cell in the grid. For every cell that contains gold (> 0), initiate a backtracking process starting from that cell.
Recursive Backtracking Function (dfs):
- Parameters:
  - i: Current row index.
  - j: Current column index.
  - currentGold: The total gold collected so far.
- Base Case:
  - If the current cell (i, j) is out of bounds, blocked (0), or already visited, terminate this path.
  - If the destination (m-1, n-1) is reached, update maxGold if currentGold is greater than the current maxGold.
- Recursive Case:
  - Add the gold in the current cell to currentGold.
  - Mark the current cell as visited by setting its value to 0 to avoid revisiting.
  - Explore all four possible directions (U, D, L, R) by recursively calling dfs on adjacent cells.
  - After exploring all directions, backtrack by restoring the gold in the current cell to its original value to allow its use in other paths.
Handle Edge Cases:
- If the source cell (0, 0) is blocked (0), return 0 as no path exists.
- After exploring all possible paths from all starting cells, return the maxGold.

Time & Space Complexity

Time Complexity: O(4^k), where k is the number of cells containing gold.
- Each cell with gold can lead to up to four directions, resulting in exponential growth with the number of gold-containing cells.
Space Complexity: O(k),
- The recursion stack can go as deep as the number of gold-containing cells, and the space required to store the path is proportional to k.

Code Snippet

Dry Run

Let's perform a dry run with the following input:

Goal: Find the maximum amount of gold the rat can collect by traversing from any starting cell with gold to the destination.

Steps:

Initial Setup:
- maxGold = 0
- Iterate through each cell to find cells with gold (> 0).
Starting from Cell (0, 0) with gold 1:
- Path: 1
- **Mark (0, 0) as visited (0).
- Move Down to (1, 0) with gold 2:
  - Path: 1 → 2 (Total: 3)
  - **Mark (1, 0) as visited (0).
  - Move Down to (2, 0) with gold 3:
    - Path: 1 → 2 → 3 (Total: 6)
    - **Mark (2, 0) as visited (0).
    - Move Right to (2, 1) with gold 4:
      - Path: 1 → 2 → 3 → 4 (Total: 10)
      - **Mark (2, 1) as visited (0).
      - Move Right to (2, 2) with gold 5:
        
        Path: 1 → 2 → 3 → 4 → 5 (Total: 15)
        
        **Mark (2, 2) as visited (0).
        
        Move Down to (3, 2) with gold 0: Blocked. Backtrack.
        
        Move Up to (1, 2) with gold 6:
        
        Path: 1 → 2 → 3 → 4 → 5 → 6 (Total: 21)
        
        **Mark (1, 2) as visited (0).
        
        Move Down to (2, 2) with gold 0: Blocked. Backtrack.
        
        Move Right to (1, 3) with gold 0: Out of bounds. Backtrack.
        
        Move Left to (1, 1) with gold 0: Blocked. Backtrack.
        
        Move Up to (0, 2) with gold 7:
        
        Path: 1 → 2 → 3 → 4 → 5 → 6 → 7 (Total: 28)
        
        **Mark (0, 2) as visited (0).
        
        Move Down to (1, 2) with gold 0: Blocked. Backtrack.
        
        Move Up to (-1, 2) with gold 0: Out of bounds. Backtrack.
        
        Move Left to (0, 1) with gold 0: Blocked. Backtrack.
        
        Move Right to (0, 3) with gold 0: Out of bounds. Backtrack.
        
        Backtrack: Unmark (0, 2) and update maxGold = 28.
        
        Backtrack: Unmark (1, 2) and (2, 2).
      - Backtrack: Unmark (2, 1) and (2, 2).
    - Backtrack: Unmark (2, 0) and (2, 1).
  - Move Right to (1, 1) with gold 0: Blocked. Backtrack.
  - Move Up to (0, 0) with gold 0: Already visited. Backtrack.
  - Move Left to (1, -1) with gold 0: Out of bounds. Backtrack.
  - Backtrack: Unmark (1, 0) and (1, 1).
- Move Right to (0, 1) with gold 0: Blocked. Backtrack.
- Move Up to (-1, 0) with gold 0: Out of bounds. Backtrack.
- Move Left to (0, -1) with gold 0: Out of bounds. Backtrack.
- Backtrack: Unmark (0, 0).
Continue Iterating Through the Grid:
- Starting from Cell (0, 2) with gold 7:
  - Similar exploration will lead to paths like 7 → 6 → 5 → 4 → 3 → 2 → 1, totaling less than or equal to 28.
  - No new maximum found.
- Starting from Other Cells:
  - Paths from other starting cells will either be blocked or lead to totals less than 28.
Final Result:
- maxGold = 28

Code Snippet

5. Dry Run

Let's perform a dry run with the following input:

Goal: Find the maximum amount of gold the rat can collect by traversing from any starting cell with gold to the destination.

Steps:

Initial Setup:
- maxGold = 0
- Iterate through each cell to find cells with gold (> 0).
Starting from Cell (0, 0) with gold 1:
- Path: 1
- **Mark (0, 0) as visited (0).
- Move Down to (1, 0) with gold 2:
  - Path: 1 → 2 (Total: 3)
  - **Mark (1, 0) as visited (0).
  - Move Down to (2, 0) with gold 3:
    - Path: 1 → 2 → 3 (Total: 6)
    - **Mark (2, 0) as visited (0).
    - Move Right to (2, 1) with gold 4:
      - Path: 1 → 2 → 3 → 4 (Total: 10)
      - **Mark (2, 1) as visited (0).
      - Move Right to (2, 2) with gold 5:
        
        Path: 1 → 2 → 3 → 4 → 5 (Total: 15)
        
        **Mark (2, 2) as visited (0).
        
        Move Down to (3, 2) with gold 0: Blocked. Backtrack.
        
        Move Up to (1, 2) with gold 6:
        
        Path: 1 → 2 → 3 → 4 → 5 → 6 (Total: 21)
        
        **Mark (1, 2) as visited (0).
        
        Move Down to (2, 2) with gold 0: Blocked. Backtrack.
        
        Move Right to (1, 3) with gold 0: Out of bounds. Backtrack.
        
        Move Left to (1, 1) with gold 0: Blocked. Backtrack.
        
        Move Up to (0, 2) with gold 7:
        
        Path: 1 → 2 → 3 → 4 → 5 → 6 → 7 (Total: 28)
        
        **Mark (0, 2) as visited (0).
        
        Move Down to (1, 2) with gold 0: Blocked. Backtrack.
        
        Move Up to (-1, 2) with gold 0: Out of bounds. Backtrack.
        
        Move Left to (0, 1) with gold 0: Blocked. Backtrack.
        
        Move Right to (0, 3) with gold 0: Out of bounds. Backtrack.
        
        Backtrack: Unmark (0, 2) and update maxGold = 28.
        
        Backtrack: Unmark (1, 2) and (2, 2).
      - Backtrack: Unmark (2, 1) and (2, 2).
    - Backtrack: Unmark (2, 0) and (2, 1).
  - Move Right to (1, 1) with gold 0: Blocked. Backtrack.
  - Move Up to (0, 0) with gold 0: Already visited. Backtrack.
  - Move Left to (1, -1) with gold 0: Out of bounds. Backtrack.
  - Backtrack: Unmark (1, 0) and (1, 1).
- Move Right to (0, 1) with gold 0: Blocked. Backtrack.
- Move Up to (-1, 0) with gold 0: Out of bounds. Backtrack.
- Move Left to (0, -1) with gold 0: Out of bounds. Backtrack.
- Backtrack: Unmark (0, 0).
Starting from Cell (0, 2) with gold 7:
- Path: 7
- **Mark (0, 2) as visited (0).
- Move Down to (1, 2) with gold 6:
  - Path: 7 → 6 (Total: 13)
  - **Mark (1, 2) as visited (0).
  - Move Down to (2, 2) with gold 5:
    - Path: 7 → 6 → 5 (Total: 18)
    - **Mark (2, 2) as visited (0).
    - Move Down to (3, 2) with gold 0: Blocked. Backtrack.
    - Move Up to (1, 2) with gold 0: Already visited. Backtrack.
    - Move Right to (2, 3) with gold 0: Out of bounds. Backtrack.
    - Move Left to (2, 1) with gold 4:
      - Path: 7 → 6 → 5 → 4 (Total: 22)
      - **Mark (2, 1) as visited (0).
      - Move Down to (3, 1) with gold 3:
        
        Path: 7 → 6 → 5 → 4 → 3 (Total: 25)
        
        **Mark (3, 1) as visited (0).
        
        Move Down to (4, 1) with gold 0: Blocked. Backtrack.
        
        Move Up to (2, 1) with gold 0: Already visited. Backtrack.
        
        Move Right to (3, 2) with gold 0: Blocked. Backtrack.
        
        Move Left to (3, 0) with gold 0: Blocked. Backtrack.
      - Backtrack: Unmark (3, 1) and (3, 0).
      - Move Up to (1, 1) with gold 0: Blocked. Backtrack.
      - Move Right to (2, 2) with gold 0: Already visited. Backtrack.
      - Move Left to (2, 0) with gold 3:
        
        Path: 7 → 6 → 5 → 4 → 3 → 3 (Invalid as cell (3, 0) is 0. Backtrack.)
      - Backtrack: Unmark (2, 1) and (2, 2).
    - Backtrack: Unmark (2, 2) and (2, 1).
  - Move Right to (1, 3) with gold 0: Out of bounds. Backtrack.
  - Move Left to (1, 1) with gold 0: Blocked. Backtrack.
  - Move Up to (0, 2) with gold 0: Already visited. Backtrack.
  - Backtrack: Unmark (1, 2) and (1, 3).
- Move Right to (0, 3) with gold 0: Out of bounds. Backtrack.
- Move Up to (-1, 2) with gold 0: Out of bounds. Backtrack.
- Move Left to (0, 1) with gold 0: Blocked. Backtrack.
- Backtrack: Unmark (0, 2).
Continuing Iteration:
- Starting from other cells with gold will either lead to blocked paths or paths with totals less than 28.
Final Result:
- maxGold = 28

Complexity Analysis

Time Complexity: O(4^k)
- Where k is the number of cells containing gold.
- Each gold cell can lead to up to four directions, resulting in exponential growth with the number of gold-containing cells.
Space Complexity: O(k)
- The recursion stack can go as deep as the number of gold-containing cells.
- The space required to store the path is proportional to k.

Optimizations:

Pruning Invalid Paths:
- By checking the validity of each move (within bounds, not blocked, not visited), we avoid unnecessary recursive calls.
Early Termination:
- If the current path's potential gold sum cannot exceed the current maxGold, terminate the path early (optional optimization).
Handling Limited Gold Cells:
- Given the constraint that there are at most 25 cells containing gold, the exponential time complexity remains manageable.

Conclusion

The Path with Maximum Gold problem is a classic example of using recursive backtracking to explore all possible paths in a grid while adhering to specific constraints. By systematically choosing directions to move, keeping track of visited cells, and accumulating the gold collected along the way, we can efficiently determine the path that yields the maximum gold.

Understanding this approach not only helps in solving similar grid-based traversal problems but also reinforces fundamental concepts in recursion, backtracking, and algorithm optimization. Implementing the solution in a functional style without using classes makes the code more concise and easier to understand, especially for beginners. By carefully managing the state and making strategic choices at each step, complex traversal problems become manageable and solvable with clarity and confidence.

Previous Next