We are in a Manhattan-type city with north-south directed avenues labeled "A" to "Z" and east-west directed streets numbered 1 to 50. A crossing is represented by the label of the avenue followed by the label of the street defining that crossing, with no leading zeros (e.g., the crossing between avenue "D" and street number 12 is represented as "D12").
The figure below shows part of the city (avenues E to G, streets 2 to 4). The distance between neighboring streets and between neighboring avenues will be the same for all pairs of neighboring avenues or streets, and will be given by the input parameter distance (in meters). This distance is measured from the center of the streets or avenues, as shown in the figure. Further, all streets and avenues will have the same width, which will be given by the input parameter width (also in meters), as shown in the figure.
Given distance and width as defined above, as well as the representation of two crossings, start and target (formatted as described above), return the minimum distance you have to travel (in meters) beginning from the center of the crossing start to reach the center of the crossing target if you are only allowed to travel on streets and avenues. For example, if start is "F3" (the red dot in the figure above) and target is "G2" (the blue dot), the green line shows one possible optimal path to go from start to target (another optimal path with the same length would be to go first south to the north-east corner of crossing "F2" and then to the east to our target).
|