Tomb Raider: Grid Pathfinding with Traps and Treasures

Question

## Problem

You are given a 2D grid representing an ancient tomb. Each cell is one of:
- `'.'` — open path
- `'#'` — wall
- `'T'` — trap (costs 2 moves to pass through)
- `'G'` — gold (must be collected on the way)

Find the minimum-cost path from the top-left `(0,0)` to the bottom-right `(n-1, m-1)` that collects **all** gold cells. Return -1 if no such path exists.

```python
def min_cost_tomb(grid: list[list[str]]) -> int:
    pass
```

## Example

```
Input:
grid = [
  ['.', 'G', '#'],
  ['.', 'T', '.'],
  ['.', '.', 'G']
]

Output: 5
# path: (0,0)->(1,0)->(2,0)->(2,1)->(1,1)[trap,+2]->(0,1)[gold]->(1,1)->(2,1)->(2,2)[gold]
# Note: must revisit to collect all gold
```

## Follow-ups

1. What if gold has individual point values and you want to maximize score within a move budget?
2. How does the complexity change as the number of gold cells grows? What is the tightest bound?
3. Can you optimize for the case where gold cells are sparse (fewer than 10)?
4. How would you extend this to a 3D tomb (x, y, z coordinates)?

Tomb Raider: Grid Pathfinding with Traps and Treasures

Question Details

Full Details

Topics

More from Karat