A ladle is carried across a foundry laid out as a grid of R rows and C columns. Each cell holds a non-negative heat cost that is added to the running total when the ladle enters that cell (the starting top-left cell is always entered). The ladle begins at the top-left cell and must reach the bottom-right cell, moving on each step to the cell immediately to the right or immediately below.
Determine the minimum possible total heat over all such routes.
Line 1: two integers R and C.
Next R lines: each contains C non-negative integers, the heat costs of that row.
A single integer: the minimum total heat of a right/down route from the top-left cell to the bottom-right cell.
Example 1
Input
3 3 1 3 1 1 5 1 4 2 1
Expected
7
Explanation
The route 1 -> 3 -> 1 (top row) then down 1 -> 1 sums to 1+3+1+1+1 = 7, which is the smallest achievable.
Example 2
Input
1 4 2 0 5 1
Expected
8
Explanation
A single row forces all rightward moves, so the total is 2+0+5+1 = 8.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →