Minimum Initial Health in a Dungeon - Intuit Online Assessment IGTDUW

Problem Preview

"A tax collector must travel through an **N × M** dungeon to collect revenue records. Each cell in the dungeon affects the collector's Health Points (HP): * A **positive** value increases HP. * A **negative** value decreases HP. * **0** has no effect. The collector starts at the **top-left** cell `(0,0)` and must reach the **bottom-right** cell `(N-1, M-1)`. At every step, the collector may move only: * Right * Down The collector's HP must **never drop to 0 or below** at any point during the journey. Determine the **minimum initial HP** required to guarantee survival until reaching the destination. --- ## Input Format * The first line contains an integer **N**, representing the number of rows. * The second line contains an integer **M**, representing the number of columns. * The next **N** lines each contain **M** space-separated integers representing the dungeon grid. --- ## Output Format Print a single integer representing the minimum initial HP required. --- ## Constraints * `1 ≤ N, M ≤ 200` * `-1000 ≤ dungeon[i][j] ≤ 1000` --- ## Sample Input ```text 3 3 -2 -3 3 -5 -10 1 10 30 -5 ``` ## Sample Output ```text 7 ``` --- ## Explanation Starting with **7 HP**, one optimal path is: ```text (0,0) → (0,1) → (0,2) → (1,2) → (2,2) ``` HP during the journey: ```text 7 → 5 → 2 → 5 → 6 → 1 ``` The HP never becomes `0` or negative, so the minimum required initial HP is **7**."