Problem L
Fastest Available Route
Your GPS has been directing you to an unknown destination for the past several hours. You are curious about where it will take you to, and how long the remaining drive will be. You try to look at the display of your GPS to find out.
The screen of your GPS can be modeled as an $w$ by $h$ grid. Each cell represents an $s$ meter by $s$ meter square of actual space, where $s$ is a power of 10. Each cell can display the following characters:
-
@ indicates your current location is on the center of this square.
-
$ indicates that your destination is on the center of this square.
-
# is a cell that is not on your current path.
-
. is a cell that is on your current path. We call these cells, as well as the start and end locations, path cells.
-
Any lowercase Latin character is part of a label. The cell the character is on is not on your current path.
You wish to find the total remaining distance until your destination arrives. Formally, let $P_1, P_2, \cdots , P_ k$ be some sequence of cells on the GPS such that
-
$P_1$ is your starting cell.
-
$P_ k$ is your ending cell.
-
$P_ i$ is a path cell, for every $1 < i < k$.
-
$P_{i-1}$ and $P_ i$ are adjacent, for every $2 < i < k$.
-
$P_ i$ and $P_ j$ are not adjacent, for every $1 \leq i, j \leq k$ such that $i + 1 < j$.
-
All cells that are not equal to some $P_ i$ are not path cells.
It is guaranteed that such a sequence of cells exists.
The length of the route represented by the GPS is the length of the shortest path that passes through the centers of $P_1, P_2, \dots , P_ k$, in that order. Find the length of your route.
Input
The first line of input contains three space-separated integers $h$ and $w$ ($1 \leq h, w \leq 580$), the dimensions of your GPS’s display, and $s$ ($10 \leq s \leq 10^{18}$), the scale of the GPS’s display.
The following $h$ lines each contain $w$ characters, which are each one of the characters mentioned above. It is guaranteed that there will be exactly one @ and # in this grid.
Output
On a single line, output “Your destination will arrive in x meters” (without quotes), where “x” is replaced by the actual length of the path.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 20 10 #########$###maize## mandela##.###hq##### #county##.......#### ###############.#### ##moonlight####.#### ##acres########.#### ###############.#### ###############.#### ###@............#### ####bons#burgers#### |
Your destination will arrive in 260 meters |
