ZOJ Problem Set - 1781
Afshung-Pizza chain, a door-to-door pizza delivery service for Hamedung, a Sildavya district, needs your help for fastest possible pizza delivery plan. With a GIS device that shows all streets of the Hamedung, each delivery boy can find a fast route to deliver the pizza to the place of order. The Elyasung Company that sells and supports this GIS device needs your help to reprogram the device to provide even a faster route plan.
Hamedung is a rectangular shape district with many two-way streets that are all rectilinear. To show the map, the GIS device uses text characters as shown in the sample test data. In this format, each one kilometer of a street is shown by a dash (-) or a pipe (|) showing that the street is either in west-east or in north-south direction. A plus (+) on the map indicates a sharp 90 degree turn (with length zero) on that position without any traffic light. All such turns are marked with +. An intersection is shown by an integer �� on that position. �� is the timing of the traffic light at that intersection which can be either three or four way. To have a smooth and accident-free district, the municipality of Hamedung has forced that every traffic light has only one green light and two or three red lights for three or four intersections respectively. One of the lights in that intersection remains green for �� minutes (i.e., during [x, x + ��) time for some x) and others are red. In the next �� minutes, one other direction turns green as if the green light turns counter clockwise. This rule is observed in all intersections.
The time is set to zero at the beginning when the delivery boy starts moving. At this time, all traffic signals are set such that only the southern light (or the northern light if no southern light exists) of each intersection is set to green, and other lights at this intersection are set to red.
Note that the only positions that the driver can change his direction are: a turn (+), or an intersection (represented by a digit). As an example, if we have a pattern like -|- in the map, the driver cannot cross the pipe if he is moving from left to right or right to left, neither can he turn left or right, since there is no intersection at this location.
Given the complete map described above, the location of an Afshung-Pizza branch, marked by S, and the location of the final delivery place, marked by D, you are to write a program for GIS device to automatically find the fastest possible route to deliver pizza from S to D. Note the following assumptions:
Source: Asia 2002, Tehran (Iran)