Problem D
All is Well
“All is well!” cries the watchman as he makes his way through the city. Each night he patrols the city, following a route that ensures that the people of the town hear him. You feel safe and secure each night as you start to fall asleep and hear the familiar call from the street below.
The watchman is tired of walking, and has asked you to find a shorter route. He has a map of the city, laid out as a grid, where each cell represents an area of $1$ by $1$ kilometer. Some cells are where people live, and the watchman cannot enter those. The other cells take him different amounts of time to enter. He always starts his route by entering the upper-left cell (unless a person is in that cell, in which case he is unable to make any route). When he walks from one cell to another, he can move either horizontally or vertically (but not diagonally).
The people are identified using uppercase English letters A–Z, and need to be visited in that order. The watchman knows where each person lives, and also how close he needs to be to them so they can hear him. He is excellent at yelling: as long as he is within hearing range of a person, he can yell and make sure that only that person hears him, even if he is within hearing range of other people.
A person can hear the watchman if the watchman enters a cell on the map such that the Euclidean distance from the center of the watchman’s cell to the center of the person’s cell is less than or equal to the person’s hearing range. If the number of rows between the watchman and person is $dr$ and the number of columns between the watchman and person is $dc$, then the distance between the watchman and the person is $\sqrt {{dr}^2 + {dc}^2}$.
Please help the watchman find an efficient route!
Input
The input starts with a line with three integers $r$, $c$, and $p$ where $1 \leq r, c \leq 100$ and $1 \leq p \leq 26$. The values $r$ and $c$ are the number of rows and columns in the grid representing the city and $p$ is the number of people who need to hear the watchman. They are identified by the first $p$ uppercase letters of the English alphabet (the first person is A, the second is B, and so on).
The next $p$ lines describe the hearing ranges of those people, in that same order. Each line has an integer $1 \leq h_ i \leq 15$ indicating the range that person $i$ can hear (in kilometers).
The next $r$ lines describe the map. Each line has $c$ space-separated tokens. Each token is either an integer $0 \leq w \leq 1\, 000$ or a uppercase English letter. If the value is an integer, it is the amount of time (in minutes) it takes to enter that cell of the grid. If the value is a letter, it indicates where the person identified by that letter is located. The first $p$ uppercase letters of the alphabet (and only those letters) appear in the grid.
Output
If a route can be found, output the least amount of time (in minutes) that it takes for the watchman to have the people hear him in alphabetic order. If there is no valid route, output $-1$.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 10 2 1 3 1 10 10 10 10 10 10 10 10 10 1 10 10 10 10 10 10 10 10 10 1 10 10 10 10 10 10 10 10 10 1 10 10 10 10 10 10 10 10 10 1 10 10 10 1 1 1 1 10 10 1 10 10 10 1 10 10 10 10 10 1 10 10 10 1 10 1 1 1 10 1 10 10 10 1 10 10 10 1 10 1 10 10 10 1 10 10 10 1 1 1 1 1 1 1 1 10 10 B A |
33 |
