Objective
Find the most expensive path from the top-left of a square grid to the bottom-right such that its total cost is below a given threshold.
Scenario
- You are given a square
NxN
grid. - You are given a maximum cost.
- Every cell in the grid has a cost. The top-left cell has cost
0
. - The cost of a path is the sum of the costs of the cells in the path. Its "cost surplus" is the result of subtracting its cost from the maximum cost.
- Movement is always either right one cell or down one cell.
- The starting point is the top-left cell of the grid and the goal is the bottom-right cell.
- You must output the smallest cost surplus of any path with a non-negative cost surplus, or -1 if there is no such path (The maximum cost is not enough).
Input restrictions
N
will be between 1 and 20 inclusive.- The maximum cost will be between 1 and 200 inclusive.
- The cost of each cell will be between 0 and 10 inclusive.
Examples
Maximum cost: 9
Grid:0 1 5 2 3 2 2 3 2
Expected output: 0
Explanation: there is a path0 2 2 3 2
with cost 9 and cost surplus 0.Maximum cost: 15
Grid:0 1 5 2 3 2 2 3 2
Expected output: 5
Explanation: the most expensive path is0 1 5 2 2
with cost 10 and cost surplus 5.Maximum cost: 6
Grid:0 1 5 2 3 2 2 3 2
Expected output: -1
Explanation: the least expensive path is0 1 3 2 2
with cost 8, which is greater than 6.
9 - (0+2+3+2+2) = 0
and for the second one will be down-right-down-right so it will be15 - (0+2+3+3+2) = 10
\$\endgroup\$