Bouldering
Time limit2sMemory limit512 MB
On a grid of holds with grip costs, find the minimum total Euclidean path length from the bottommost hold to the topmost hold, where consecutive holds must be within reach r and total cost stays at most s.
- Level
Medium6 of 10
- Topics
- Graph, Shortest path, Dynamic programming, Geometry
- Solved
- No attempts yet
Problem
After several long afternoons of procrastinating in his box and playing video games all night, Carl decided it was finally time to start his New Year's resolution: going to the bouldering gym.
There he picked one of the easier walls and tried to make his way up. He could never reach the top, though, because he always ran out of stamina and fell down.
While climbing he noticed that the holds have different shapes and that some are much harder to grip than others, so gripping them costs different amounts of stamina. Frustrated, he asks one of the regulars at the bouldering gym how to scale the wall, which is you. Show him the shortest way up that he can take without running out of stamina.
The bouldering wall is a rectangular grid of cells of size 1 × 1 where holds can be installed. We do not consider the varying sizes of the holds, so you can assume each hold is a single point exactly at the center of its cell. Carl can move from one hold to another only if the distance between them (the Euclidean distance between the cell centers) does not exceed his arms' reach.
Figure B.1: Sample test case 1
Input
The input consists of:
- A line with four integers h, w, r, and s (2 ≤ h ≤ 25, 1 ≤ w ≤ 25, 1 ≤ r ≤ 3, 1 ≤ s ≤ 10^9), where h and w are the height and width of the bouldering wall, r is the reach of Carl's arms, and s is a numerical representation of Carl's stamina.
- h lines, each with w characters, describing the holds on the bouldering wall. Each character is either a digit c (1 ≤ c ≤ 9), which means a hold with difficulty c is installed at this position, or ".", which means no hold is installed.
The first line corresponds to the top of the bouldering wall and the last line to the bottom.
A sequence of holds is a valid route for Carl if the following conditions are satisfied:
- The route starts at the bottommost hold and ends at the topmost hold. There is always a unique bottommost and a unique topmost hold, and they are guaranteed to be distinct.
- The sum of the difficulty levels of the holds used is at most s.
- The Euclidean distance between any two consecutive holds along the route is at most r.
Output
Output the total length of a shortest route Carl can climb to reach the topmost hold without running out of stamina. Your answer must have an absolute or relative error of at most 10^-6. If Carl cannot reach the top, output impossible.