• 12

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

You are given an integer n, an array costs of n-1 integers and a n times n grid of digits. You start at (0, 0) with a starting cost equal to grid(0, 0) and you want to reach the bottom right (n-1, n-1) with minimal cost.

At any turn you can move from (i, j) to (i', j') (different of (i, j)) with a cost equal to the sum of:

(1) the value of the grid at (i', j'), grid(i', j')
(2) the integer at the (d-1)-th index in costs table, where d = max(abs(i-i'), abs(j-j')).

Find the minimum cost.

`Example:31 5132     X..053  -> X..011     .XXstarting cost = grid(0, 0) = 1(0, 0) -> (1, 0) = costs[1-1] + grid(1, 0) = 1 + 0 = 1(1, 0) -> (2, 1) = costs[1-1] + grid(2, 1) = 1 + 1 = 2(2, 1) -> (2, 2) = costs[1-1] + grid(2, 2) = 1 + 1 = 2total = 1 + 1 + 2 + 2 = 6`
Input
Line 1: An integer n for the number of points to compare.
Line 2: A space separated string costs with n-1 elements, representing the cost of the distance.
Next n lines: The rows of the n times n grid
Output
Line 1: An integer for the minimum cost required to reach the target.
Constraints
In costs, the n-1 integers satisfy: 0 < c_1 < c_2 < ... < c_(n-1)
3 <= n <= 40
Example
Input
```3
1 5
132
053
011```
Output
`6`

A higher resolution is required to access the IDE