Dungeon Game

Problem Statement

A knight starts at the top-left corner of a dungeon grid and must rescue a princess at the bottom-right corner. The knight can only move right or down.

Each cell contains an integer:

• Positive: health potion (knight gains health)
• Negative: demon (knight loses health)
• Zero: empty room

The knight dies if health drops to 0 or below at any point. Find the minimum initial health needed to reach the princess alive.

Dungeon:
[-2, -3,  3]
[-5,-10,  1]
[10, 30, -5]

Answer: 7

Path: Right → Right → Down → Down Health changes: -2 → -3 → 3 → 1 → -5 With initial health 7: 7 → 5 → 2 → 5 → 6 → 1 (always > 0)