Crossing the Cave

Hard

A cave is a rectangular grid cave with m rows and n columns. An explorer starts in the top-left cell and must reach the bottom-right one, moving only right or down. In every cell, the first and the last included, the explorer's energy changes by cave[i][j]: a negative number is a trap, a positive one is a food cache, and zero does nothing. If the energy ever drops to 0 or below, the explorer is out. Return the smallest positive starting energy that lets the explorer reach the exit along the best route.

Example 1

cave=[[0, -4, 2], [-1, -6, 3], [5, -2, -3]] → 2

Go down, down, right, right through 0, -1, +5, -2, -3. Starting with 2 gives 2 → 1 → 6 → 4 → 1, never reaching zero. Starting with 1 hits 0 in the second cell.

Example 2

cave=[[7]] → 1

There is a single cell and it adds energy, yet you still need to start with at least 1.

Example 3

cave=[[-3, 10, -20]] → 14

Constraints

1 ≤ m, n ≤ 200
-1000 ≤ cave[i][j] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Biggest Solid Panel Block Hard Longest Uphill Walk Hard Weeks of Rest by Flight Hard Berry Field Round Trip Hard Six-Cell Tile Slider Hard

Input

cave=[[0, -4, 2], [-1, -6, 3], [5, -2, -3]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.