Loading...
Loading...
Loading...
Karthik delivers food parcels across a town laid out as a grid of r rows and c columns of blocks. Each block has a wait time in minutes, caused by traffic and signals. He starts at the top-left block and must reach the bottom-right block.
Each move takes him one block to the right or one block down. The cost of a route is the sum of the wait times of every block on it, including the first and the last block.
Print the smallest possible cost.
Example 1
Input
3 4 2 1 9 1 3 8 1 1 1 1 2 1
Output
10
Go down, down, right, right, right: 2 + 3 + 1 + 1 + 2 + 1 = 10.
Example 2
Input
2 2 5 1 1 5
Output
11
Both routes cost 11.
Try the problem first. Open one hint at a time.
The best route into a block comes from the cheaper of two blocks: the one above it or the one on its left.
So the best cost to reach a block is its own wait time plus the smaller of those two best costs.
The top row can only be reached from the left, and the left column only from above. Their best costs are running sums.
Fill the table row by row, left to right. Use long, because a route can add up to 1999 blocks.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor